Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- using namespace std;
- long long MAX_VALUE = INT32_MAX + 1;
- struct node {
- long long value;
- long long tr_max = -MAX_VALUE;
- node(long long m) {
- value = m;
- }
- };
- typedef node *link;
- struct check {
- int left;
- int right;
- long long value;
- check(int l, int r, long long v) {
- left = l;
- right = r;
- value = v;
- }
- };
- typedef check *check_1;
- vector<link> tree;
- vector<check_1> check_tree;
- void push(int v, int left, int right) {
- if (tree[v]->tr_max != -MAX_VALUE)
- tree[v]->value = tree[v]->tr_max;
- if (left != right) {
- tree[v * 2 + 1]->tr_max = max(tree[v * 2 + 1]->tr_max, tree[v]->tr_max);
- tree[v * 2 + 2]->tr_max = max(tree[v * 2 + 2]->tr_max, tree[v]->tr_max);
- int middle = left - (left - right) / 2;
- push(2 * v + 1, left, middle);
- push(2 * v + 2, middle + 1, right);
- tree[v]->value = min(tree[v * 2 + 1]->value, tree[v * 2 + 2]->value);
- }
- }
- long long getMinValue(int a, int b, int left, int right, int v) {
- if (left > b || right < a) {
- return MAX_VALUE;
- }
- if (left >= a && right <= b) {
- return tree[v]->value;
- }
- long long new_left = getMinValue(a, b, left, left - (left - right) / 2, v * 2 + 1);
- long long new_right = getMinValue(a, b, left - (left - right) / 2 + 1, right, v * 2 + 2);
- return min(new_left, new_right);
- }
- void set(int a, int b, long long x, int v, int left, int right) {
- if (left > b || right < a)
- return;
- if (left >= a && right <= b) {
- tree[v]->tr_max = max(tree[v]->tr_max, x);
- return;
- }
- int vm = left - (left - right) / 2;
- set(a, b, x, v * 2 + 1, left, vm);
- set(a, b, x, v * 2 + 2, vm + 1, right);
- }
- int main() {
- int n, m, x = 1;
- cin >> n >> m;
- while (x < n) {
- x <<= 1;
- }
- tree.resize(x * 2 - 1);
- check_tree.resize(m);
- for (auto &i : tree) {
- i = new node(MAX_VALUE);
- }
- int l, r, j = 0;
- long long v;
- while (cin >> l) {
- cin >> r >> v;
- check_tree[j++] = new check(l - 1, r - 1, v);
- set(l - 1, r - 1, v, 0, 0, x - 1);
- }
- push(0, 0, x - 1);
- for (int i = 0; i < m; i++) {
- if (getMinValue(check_tree[i]->left, check_tree[i]->right, 0, x - 1, 0)
- != check_tree[i]->value) {
- cout << "inconsistent";
- return 0;
- }
- }
- cout << "consistent\n";
- for (int i = x - 1; i < x - 1 + n; i++) {
- if (tree[i]->value == MAX_VALUE) {
- cout << (1ll << 31) - 1 << " ";
- continue;
- }
- cout << tree[i]->value << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement