Submission #899451

#	Time	Username	Problem	Language	Result	Execution time	Memory
899451		pan	RMQ (NOI17_rmq)	C++17	100 / 100	77 ms	18496 KiB

rmq

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
ll const INF = 1e9;
ll n,q;
ll minl ,maxl, minr, maxr;
vector<vector<pi> >queries;
vector<vector<ll> > newq;
vector<ll> ans;
struct node{
    int s, e, m; //range is [s,e], m is the middle point
    ll val, pos; //sum of [s,e]
    ll lazy; //lazy tag of [s,e]
    node *l, *r; //create two children l and r, where l is [s,m] and [m+1,e]
    node (int S, int E){ //constructor called node
       s = S, e = E, m = (s+e)/2;
       val = 0; 
       pos = s;//initially all values are 0
       lazy = 0; //lazy tag of 0 will mean there is no update (sentinel value)
       l=r=nullptr;

	}
	void create()
	{
		if(s != e && l==nullptr){ //node is not yet a leaf, so create two children
		     l = new node(s, m); //create left child
             r = new node(m+1, e); //create right child
		 }
	}
 
    void propogate(){
       if (lazy==0) return; //nothing happens
       create();
       val+=lazy; //(e-s+1) is the length of the range
       if (s != e){ //not a leaf, send lazy tags to children
           l->lazy+=lazy;
           r->lazy+=lazy;
       }
       lazy=0; //set our lazy tag value back to the sentinel
    }
    void update(int S, int E, ll V){ //increment [S,E] by V
	   propogate();
       if(s==S && e==E) lazy += V; //update covers range, update lazy tag
       else{ //go we have to go deeper
		   create();
           if(E <= m) l->update(S, E, V); //[S,E] is in the left child
           else if (m < S) r->update(S, E, V); //[S,E] is in the right child
           else l->update(S, m, V),r->update(m+1, E, V);
           l->propogate(),r->propogate();
           //remember to propogate your children before update yourself
           if (l->val<=r->val) {val = l->val, pos = l-> pos;}
           else {val = r->val, pos = r-> pos;}
       }
    }
    pi query(int S, int E){
       propogate(); //remember to propogate
       if(s == S && e == E) {return mp(val, pos); }//case 1
       create();
       if(E <= m) {return l->query(S, E);} //case 2, recurse to left child
       else if(S >= m+1) {return r->query(S, E);} //case 3, recurse to right child
       else //case 4, split the query range, recurse to both childs
       {
			pi a = l->query(S, m), b = r->query(m+1, E); 
			if (a.f<=b.f) return a;
			else return b;
	   }
			
}
} *root;

void merge(pi a)
{
	minl = min(minl, a.f);
	maxl = max(maxl, a.f);
	minr = min(minr, a.s);
	maxr = max(maxr, a.s);
}

void end()
{
	while (n--) cout << -1 << ' ';
}

int main()
{
	cin >> n >> q;
	queries.resize(n);
	newq.resize(n);
	ans.resize(n);
	for (ll i=0; i<q; ++i)
	{
		ll a, b ,c;
		cin >> a >> b >> c;
		queries[c].pb(mp(a,b));
	}
	root = new node(0, n-1);
	for (ll i=n-1; i>=0; --i)
	{
		if (!queries[i].empty())
		{
			minl=INF, maxl = -1, minr= INF, maxr = -1;
			for (pi u: queries[i]) merge(u);
			//show3(minl, maxl, minr);
			//show(maxr);
			if (maxl>minr) {end(); return 0;}
			root->update(minl, maxr, 1);
			newq[i].pb(minl);
			newq[i].pb(maxl);
			newq[i].pb(minr);
			newq[i].pb(maxr);
		}
	}
	
	for (ll i=0; i<n; ++i)
	{
		if (!newq[i].empty())
		{
			root->update(newq[i][0], newq[i][3], -1);
			pi ret = root->query(newq[i][1], newq[i][2]);
			if (ret.f>0) {end(); return 0;}
			root->update(ret.s, ret.s, INF);
			ans[ret.s] = i;
		}
		else
		{
			pi ret = root->query(0, n-1);
			if (ret.f>0) {end(); return 0;}
			root->update(ret.s, ret.s, INF);
			ans[ret.s] = i;
		}
		
	}
	for (ll u: ans) cout << u << ' ';
	
	
	return 0;
}

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