Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef __int128 lll;
- typedef long long ll;
- typedef double ld;
- ll inf = 1e9+1, mod = 1e9 + 7;
- const int N = 1e6;
- #define all(a) a.begin(),a.end()
- #define pb push_back
- #define _GLIBCXX_DEBUG
- struct test
- {
- ll l, r, ind;
- };
- std::vector<test>arr;
- ll a[N], u[N*4], tree[N*4];
- bool compare(test a, test b){
- if(a.ind != b.ind) return a.ind < b.ind;
- else if(a.l != b.l) return a.l < b.l;
- else return a.r < b.r;
- }
- void build(ll l, ll r, ll v) {
- if (l == r) {
- tree[v] = a[l];
- return;
- }
- ll m = (l + r) / 2;
- build(l, m, v + v);
- build(m + 1, r, v + v + 1);
- tree[v] = min(tree[v + v], tree[v + v + 1]);
- }
- void push(ll l, ll r, ll v) {
- if (u[v]==-inf)
- return;
- tree[v] = u[v];
- if (l == r) {
- u[v] = -inf;
- return;
- }
- u[v + v] = u[v];
- u[v + v + 1] = u[v];
- u[v] = -inf;
- }
- void change(ll l, ll r, ll v, ll la, ll ra, ll x) {
- push(l, r, v);
- if (l > ra || r < la)
- return;
- if (l >= la && r <= ra) {
- u[v] = x;
- push(l, r, v);
- return;
- }
- ll m = (l + r) / 2;
- change(l, m, v + v, la, ra, x);
- change(m + 1, r, v + v + 1, la, ra, x);
- tree[v] = min(tree[v + v],tree[v + v + 1]);
- }
- ll ans(ll l, ll r, ll v, ll la, ll ra) {
- push(l, r, v);
- if (l > ra || r < la)
- return inf;
- if (l >= la && r <= ra)
- return tree[v];
- ll m = (l + r) / 2;
- return min(ans(l, m, v + v, la, ra),ans(m + 1, r, v + v + 1, la, ra));
- }
- void dfs(ll v, ll tl, ll tr){
- if(tl!=tr){
- ll m = (tl+tr)/2;
- dfs(v+v, tl, m);
- dfs(v+v+1, m+1, tr);
- }
- else cout << tree[v] << ' ';
- }
- int main() {
- #ifdef anime
- freopen("input1.txt", "r", stdin);
- freopen("outpu1.txt", "w", stdout);
- #endif
- srand(time(nullptr));
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- ll n, k;
- cin >> n;
- cin >> k;
- build(1, n, 1);
- while (k--) {
- ll x, y;
- cin >> x >> y;
- ll z;
- cin >> z;
- arr.pb({x,y,z});
- }
- sort(arr.begin(), arr.end(), compare);
- for(int i = 0; i < arr.size(); ++i){
- ll x = arr[i].l, y = arr[i].r, z = arr[i].ind;
- change(1, n, 1, x, y, z);
- }
- for(int i = 0; i < arr.size(); ++i){
- ll na = ans(1, n, 1, arr[i].l, arr[i].r);
- ll nb = arr[i].ind;
- if(na!=nb){
- cout << "inconsistent";
- return 0;
- }
- }
- cout << "consistent" << '\n';
- dfs(1, 1, n);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
