482B


  Posted on 29 Nov 2014
consecutive algorithms

Solution


#include <cstdio>
#include <algorithm>
using namespace std;

#define MAX_M 100005
#define MAX_N 100005
#define MAX_BIT_NUM 40
#define D(x) x

struct Condition
{
	int l, r, q;
}condition[MAX_M];

int n, m;
int seq[MAX_N][MAX_BIT_NUM];
int delta[MAX_N][MAX_BIT_NUM];
int sum[MAX_N][MAX_BIT_NUM];

void input()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		condition[i].l = a;
		condition[i].r = b;
		condition[i].q = c;
	}
}

int get_bit(int l, int r, int pos)
{
	int temp = sum[r][pos] - sum[l - 1][pos] - (r - l + 1);
	if (temp == 0)
		return 1;
	return 0;
}

int work()
{
	for (int i = 0; i < m; i++)
	{
		int q = condition[i].q;
		for (int j = 0; q; q >>= 1, j++)
		{
			if (q & 1)
			{
				delta[condition[i].l][j] += 1;
				delta[condition[i].r + 1][j] += -1;
			}
		}
	}

	int temp[MAX_BIT_NUM];
	fill(temp, temp + MAX_BIT_NUM, 0);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < MAX_BIT_NUM; j++)
		{
			temp[j] += delta[i][j];
			if (temp[j])
			{
				seq[i][j] = 1;
			}
			sum[i][j] = sum[i - 1][j] + seq[i][j];
		}
	}

	for (int i = 0; i < m; i++)
	{
		int q = condition[i].q;
		for (int j = 0; j <= 30; j++, q >>= 1)
		{
			if (get_bit(condition[i].l, condition[i].r, j) != (q & 1))
			{
				return false;
			}
		}
	}
	return true;
}

int get_value(int pos)
{
	int ret = 0;
	for (int i = 30; i >= 0; i--)
	{
		ret = (ret << 1) + seq[pos][i];
	}
	return ret;
}

void output()
{
	printf("%d", get_value(1));
	for (int i = 2; i <= n; i++)
	{
		printf(" %d", get_value(i));
	}
	puts("");
}

int main()
{
	input();
	if (work())
	{
		puts("YES");
		output();
	}else
	{
		puts("NO");
	}
	return 0;
}