Submission #369296

#	Time	Username	Problem	Language	Result	Execution time	Memory
369296		jamezzz	RMQ (NOI17_rmq)	C++14	23 / 100	5 ms	5120 KiB

rmq

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

#define fi first
#define se second
#define pb emplace_back
#define ll long long
#define INF 1023456789
#define INFll 1023456789123456789
#define all(x) x.begin(), x.end()
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

struct node{
	int s,e,m,v,lz;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;v=-1;lz=-1;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		v=max(v,lz);
		if(s!=e){
			l->lz=max(l->lz,lz);
			r->lz=max(r->lz,lz);
		}
		lz=-1;
	}
	
	void up(int x,int y,int nv){
		if(s==x&&e==y){
			lz=max(lz,nv);return;
		}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else{
			l->up(x,m,nv);
			r->up(m+1,y,nv);
		}
		l->propo();r->propo();
		v=max(l->v,r->v);
	}
	
	int qry(int x){
		propo();
		if(s==x&&e==x)return v;
		if(x<=m)return l->qry(x);
		else return r->qry(x);
	}
}*root;
	

int n,q,l,r,a,ans[100005];
set<int> s;
vii rng[100005];
vi v[100005];

void impos(){
	for(int i=0;i<n;++i)printf("-1 ");
	exit(0);
}


int main(){
	scanf("%d%d",&n,&q);
	root=new node(0,n+5);
	for(int i=0;i<q;++i){
		scanf("%d%d%d",&l,&r,&a);
		rng[a].pb(l,r);
		root->up(l,r,a);
	}
	for(int i=0;i<n;++i){
		int val=root->qry(i);
		//printf("%d ",val);
		if(i==-1)s.insert(i);
		else v[val].pb(i);
	}
	//printf("\n");
	for(int i=0;i<n;++i){
		l=0,r=n-1;
		for(ii p:rng[i]){
			l=max(l,p.fi);
			r=min(r,p.se);
		}
		for(int x:v[i])s.insert(x);
		if(l>r)impos();
		auto it=s.lower_bound(l);
		//printf("%d: %d %d %d\n",i,*it,l,r);
		if(it==s.end()||*it>r)impos();
		ans[*it]=i;
		s.erase(it);
	}
	for(int i=0;i<n;++i)printf("%d ",ans[i]);
	printf("\n");
}

/*
5 3
0 2 1
1 3 0
1 4 0

3 2
0 1 1
1 2 1
*/

Compilation message (stderr)

rmq.cpp: In function 'int main()':
rmq.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
rmq.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |   scanf("%d%d%d",&l,&r,&a);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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