oj.uz

Submission #988716

# Submission time Handle Problem Language Result Execution time Memory
988716 2024-05-25T16:58:18 Z Acanikolic RMQ (NOI17_rmq) C++14
23 / 100
 4 ms 6492 KB 
#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);
		}
		if(get(1,1,n,1,n) != g[i].size()) {
			ok = false;
			goto kraj;
		}
		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();
		}
		if(!used) {
			ok = false;
			goto kraj;
		}
		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]);
			}
			assert(mn == i || mn == inf);
		}
	}
	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

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

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6488 KB Output is correct
3 Correct 4 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 3 ms 6488 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 3 ms 6488 KB Output is correct

Subtask #2
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6488 KB Output is correct
3 Correct 4 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 3 ms 6488 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 3 ms 6488 KB Output is correct
12 Incorrect 4 ms 6492 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 6488 KB Output is correct
3 Correct 4 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 3 ms 6488 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 3 ms 6492 KB Output is correct
11 Correct 3 ms 6488 KB Output is correct
12 Incorrect 4 ms 6492 KB Output isn't correct
13 Halted 0 ms 0 KB -