Submission #676473

#	Time	Username	Problem	Language	Result	Execution time	Memory
676473		penguin133	RMQ (NOI17_rmq)	C++17	100 / 100	59 ms	25312 KiB

rmq

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n,m,q;
vector<pi> Q[100005];
struct node{
	int s,e,m,val,lazy, pos;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		val = 0;
		lazy = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
			pos = l->pos;
		}
		else pos = s;
	}
	void propo(){
		if(lazy != 0){
			val += lazy;
			if(s != e)l->lazy += lazy, r->lazy += lazy;
			lazy = 0;
		}
	}
	void upd(int a, int b, int c){
		if(s == a && e == b)lazy += c;
		else{
			if(b <= m)l->upd(a, b,c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->propo(), r->propo();
			val = min(l->val, r->val);
			if(l->val < r->val)pos = l->pos;
			else pos = r->pos;
		}
	}
	pi query(int a, int b){
		propo();
		if(s == a && e == b)return {val, pos};
		else if(b <= m)return l->query(a, b);
		else if(a > m)return r->query(a, b);
		else return min(l->query(a, m), r->query(m+1, b));
	}
}*root;
void bye(){
	for(int i=0;i<n;i++)cout << -1 << " ";
}
pi range[100005];
int ans[100005];
vector<pi>rng[200005];
void solve(){
	cin >> n >> q;
	for(int i=1;i<=q;i++){
		int x,y,z;cin >> x >> y >> z;
		Q[z].push_back({x, y});
	}
	for(int i=0;i<n;i++)ans[i] = n;
	root = new node(0, n-1);
	vector<int>v;
	vector<int>v2;
	for(int i=n-1;i>=0;i--){
		int maxi = 0, mini = n - 1, maxi2 = 0, mini2 = n - 1;
		for(auto [j, k] : Q[i])maxi = max(maxi, j), mini = min(mini, k), maxi2 = max(maxi2, k), mini2 = min(mini2, j);
		if(maxi > mini){
			bye();return;
		}
		if(Q[i].empty()){
			v.push_back(i);
			continue;
		}
		pi tmp = root->query(maxi, mini);
		if(tmp.fi){
			bye();return;
		}
		ans[tmp.se] = i;
		v2.push_back(tmp.se);
		root->upd(mini2, maxi2, 1);
		//cerr << "ok\n";
	}
	for(auto i : v2)root->upd(i, i, 1e9);
	reverse(v.begin(), v.end());
	int in = 0;
	for(int i=0;i<=n-1;i++){
		
		if(in < v.size() && v[in] == i){
			int tmp = root->pos;
			root->propo();
			//cout << root->val << " " << i << '\n';
			if(root->val){
				bye(); return;
			}
			root->upd(tmp, tmp, 1e9);
			ans[tmp] = i;
			in++;
			continue;
			
		}
		int maxi = 0, mini = n - 1, maxi2 = 0, mini2 = n - 1;
		for(auto [j, k] : Q[i])maxi = max(maxi, j), mini = min(mini, k), maxi2 = max(maxi2, k), mini2 = min(mini2, j);
		if(mini2 <= maxi2)root->upd(mini2, maxi2, -1);
	}
	for(int i=0;i<n;i++)cout << ans[i] << " ";
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

rmq.cpp: In function 'void solve()':
rmq.cpp:91:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   if(in < v.size() && v[in] == i){
      |      ~~~^~~~~~~~~~
rmq.cpp: At global scope:
rmq.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main(){
      | ^~~~

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