Submission #988718

#	Time	Username	Problem	Language	Result	Execution time	Memory
988718		Acanikolic	RMQ (NOI17_rmq)	C++14	23 / 100	4 ms	6900 KiB

rmq

#include <bits/stdc++.h>  
  
#define pb push_back
 
#define F first
 
#define S second
 
using namespace std;
 
const long long N = 2e5 + 10;
 
const long long mod = 998244353;
 
const long long inf = 1e9;

vector<pair<int,int>>g[N];

int seg[N],lazy[N];

void push(int node,int tl,int tr) {
	seg[node] += lazy[node];
	if(tl != tr) {
		lazy[node * 2] += lazy[node];
		lazy[node * 2 + 1] += lazy[node];
	}
	lazy[node] = 0;
}

void modify(int node,int tl,int tr,int l,int r,int x) {
	push(node,tl,tr);
	if(tl > r || tr < l) return;
	if(tl >= l && tr <= r) {
		lazy[node] += x;
		push(node,tl,tr);
		return;
	}
	push(node,tl,tr);
	int mid = (tl + tr) / 2; 
	modify(node * 2,tl,mid,l,r,x);
	modify(node * 2 + 1,mid + 1,tr,l,r,x);
	seg[node] = max(seg[node * 2],seg[node * 2 + 1]);
}

int get(int node,int tl,int tr,int l,int r) {
	push(node,tl,tr);
	if(tl > r || tr < l) return 0;
	if(tl >= l && tr <= r) return seg[node];
	int mid = (tl + tr) / 2;
	return max(get(node * 2,tl,mid,l,r),get(node * 2 + 1,mid + 1,tr,l,r));
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
	int n,q;
	cin >> n >> q;
	vector<int>res(n + 1);
	for(int i = 1; i <= q; i++) {
		int l,r,x;
		cin >> l >> r >> x;
		l += 1;
		r += 1;
		x += 1;
		g[x].pb({l,r});
	}
	set<int>st;
	for(int i = 1; i <= n; i++) st.insert(i);
	vector<int>vec;
	bool ok = true;
	for(int i = n; i >= 1; i--) {
		if(!g[i].size()) {
			vec.pb(i);
			continue;
		}
		vector<int>all;
		for(auto X : g[i]) {
			int cnt = 0;
			auto lb = st.lower_bound(X.F);
			vector<int>v;
			while(lb != st.end() && *lb <= X.S) {
				cnt += 1;
				v.pb(*lb);
				all.pb(*lb);
				lb++;
			}
			for(auto XX : v) {
				st.erase(XX);
			}
			modify(1,1,n,X.F,X.S,1);
		}
		bool used = false;
		for(auto X : all) {
			if(!used && get(1,1,n,X,X) == g[i].size()) {
				used = true;
				res[X] = i;
				continue;
			}
			if(vec.empty()) {
				ok = false;
				goto kraj;
			}
			res[X] = vec.back();
			vec.pop_back();
		}
		for(auto X : g[i]) {
			modify(1,1,n,X.F,X.S,-1);
		}
	}
	kraj:;
	if(ok) {
		for(int i = 1; i <= n; i++) {
			int mn = inf;
			for(auto X : g[i]) {
				for(int j = X.F; j <= X.S; j++) mn = min(mn,res[j]);
			}
			if(mn != i && mn != inf) ok = false;
		}
	}
	if(ok) {
		for(int i = 1; i <= n; i++) cout << res[i] - 1 << " ";
	}else {
		for(int i = 1; i <= n; i++) cout << -1 << " ";
	}
    return 0;
}

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:95:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    if(!used && get(1,1,n,X,X) == g[i].size()) {
      |                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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