Submission #850900

#	Time	Username	Problem	Language	Result	Execution time	Memory
850900		annabeth9680	RMQ (NOI17_rmq)	C++17	100 / 100	178 ms	13220 KiB

rmq

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int MAXN = 1e5+11;
struct segtree{
    int T[MAXN<<2];
    void init(){
        fill(T,T+(MAXN<<2),-1);
    }
    void update(int findl, int findr, int val, int l, int r, int cur){
        if(findr < l || r < findl) return;
        if(findl <= l && r <= findr){
            T[cur] = max(T[cur],val);
            return;
        }
        T[2*cur+1] = max(T[cur],T[2*cur+1]);
        T[2*cur+2] = max(T[cur],T[2*cur+2]);
        int m = (l+r)/2;
        update(findl,findr,val,l,m,2*cur+1);
        update(findl,findr,val,m+1,r,2*cur+2);
        T[cur] = min(T[2*cur+1],T[2*cur+2]);
    }
    int query(int findl, int findr, int l, int r, int cur){
        if(findr < l || r < findl) return (1<<30);
        if(findl <= l && r <= findr) return T[cur];
        T[2*cur+1] = max(T[cur],T[2*cur+1]);
        T[2*cur+2] = max(T[cur],T[2*cur+2]);
        int m = (l+r)/2;
        return min(query(findl,findr,l,m,cur*2+1),query(findl,findr,m+1,r,cur*2+2));
    }
}seg1,seg2;
struct rmq{
    int l,r,x;
};
bool cmp(rmq a, rmq b){
    return a.r-a.l < b.r-b.l;
}
vector<rmq> qs[MAXN];
int LL[MAXN], RR[MAXN], L[MAXN], R[MAXN], ans[MAXN];
bool used[MAXN], used2[MAXN];
int main()
{
    int N,Q; cin >> N >> Q;
    vector<rmq> queries;
    for(int i = 0;i<Q;++i){
        int l,r,x; cin >> l >> r >> x;
        queries.push_back({l,r,x});
        qs[x].push_back({l,r,x});
        seg1.update(l,r,x,0,N-1,0);
    }
    auto ret = [&N](){
        for(int i = 0;i<N;++i) cout << -1 << " ";
        cout << "\n";
        exit(0);
	};
    for(int i = 0;i<Q;++i){
        int c = seg1.query(queries[i].l,queries[i].r,0,N-1,0);
        if(c != queries[i].x) ret();
    }
    for(int i = 0;i<N;++i){
        int curl = 0, curr = N-1;
        for(int j = 0;j<qs[i].size();++j){
            curl = max(curl,qs[i][j].l);
            curr = min(curr,qs[i][j].r);
            //cout << i << " " << qs[i][j].l << " " << qs[i][j].r << "\n";
        }
        if(curl > curr) ret();
        LL[i] = curl; RR[i] = curr;
    }
    for(int i = 0;i<N;++i){
        L[i] = 1<<30; R[i] = -1<<30;
    }
    for(int i = 0;i<N;++i){
        int c = seg1.query(i,i,0,N-1,0);
        if(c == -1) continue;
        if(LL[c] <= i && i <= RR[c]){
            L[c] = min(L[c],i);
            R[c] = max(R[c],i);
        }
    }
    vector<rmq> nxt;
    for(int i = 0;i<N;++i){
        if(qs[i].size()){
            if(L[i] > R[i]){
                ret();
            }
            nxt.push_back({L[i],R[i],i});
        }
    }
    sort(nxt.begin(),nxt.end(),cmp);
    auto sign = [](int i, int val){
		used[i] = true, used2[val] = true;
		ans[i] = val;
	};
	for(auto s : nxt){
        for(int j = s.l;j <= s.r;++j){
            if(!used[j]){
                sign(j,s.x);
                break;
            }
        }
	}
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	for(int i = 0;i<N;++i){
        if(!used[i]){
            int c = seg1.query(i,i,0,N-1,0);
            pq.push({c,i});
        }
	}
	for(int i = 0;i<N;++i){
        if(!used2[i]){
            int se = pq.top().s; pq.pop();
            ans[se] = i;
        }
	}
	for(int i = 0;i<N;++i) seg2.update(i,i,ans[i],0,N-1,0);
	//for(int i = 0;i<N;++i) cout << ans[i] << " ";
	//cout << "\n";
	for(int i = 0;i<Q;++i){
        int c = seg2.query(queries[i].l,queries[i].r,0,N-1,0);
        //cout << c << "\n";
        if(c != queries[i].x) ret();
	}
	for(int i = 0;i<N;++i){
        cout << ans[i] << " ";
	}
	cout << "\n";
    return 0;
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:63:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rmq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 0;j<qs[i].size();++j){
      |                       ~^~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33