Submission #490127

#	Time	Username	Problem	Language	Result	Execution time	Memory
490127		cfalas	Examination (JOI19_examination)	C++17	0 / 100	1642 ms	154660 KiB

examination

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FORi(i,a,b) for(ll i=((ll)a);i<(ll)b;i++)
#define FOR(i,n) FORi(i,0,n)
#define FOA(v,a) for(auto v : a)
#define INF 100000
#define INF2 100000
#define MID ((l+r)/2)
typedef pair<int, int> ii;
#define F first
#define S second
struct seg{
	seg* L=NULL, *R=NULL;
	int val=0;
	int pos=-1;

	void push(int l, int r){
		if(pos!=-1){
			if(pos<=MID){
				L = new seg;
				L->val = 1;
				L->pos = pos;
			}
			else{
				R = new seg;
				R->val = 1;
				R->pos = pos;
			}
			pos = -1;
		}
	}

	void update(int x, int l=0, int r=INF2){
		if(l==r && l==x) val++;
		else if(l==r) return;
		else{
			val++;
			if(!L && !R && pos==-1){
				pos = x;
				return;
			}
			push(l,r);
			if(x<=MID){
				if(!L) L = new seg;
				L->update(x,l,MID);
			}
			else{
				if(!R) R = new seg;
				R->update(x,MID+1,r);
			}
		}
	}
	int query(int rl, int rr, int l=0, int r=INF2){
		if(rl<=l && r<=rr) return val;
		else if(rr<l || r<rl) return 0;
		else{
			push(l,r);
			int ans=0;
			if(L) ans+=L->query(rl,rr,l,MID);
			if(R) ans+=R->query(rl,rr,MID+1,r);
			return ans;
		}
	}
};

struct seg2{
	seg2* L=NULL, *R=NULL;
	seg val;
	int pos=-1;

	void push(int l, int r){
		if(pos!=-1){
			if(pos<=MID){
				L = new seg2;
				L->val = val;
				L->pos = pos;
			}
			else{
				R = new seg2;
				R->val = val;
				R->pos = pos;
			}
			pos = -1;
		}
	}

	void update(ii x, int l=0, int r=INF2){
		if(l==r && l==x.F) val.update(x.S);
		else if(l==r) return;
		else{
			if(!L && !R && pos==-1){
				val.update(x.S);
				pos = x.F;
				return;
			}
			push(l,r);
			if(x.F<=MID){
				if(!L) L = new seg2;
				L->update(x,l,MID);
			}
			else{
				if(!R) R = new seg2;
				R->update(x,MID+1,r);
			}
			val.update(x.S);
		}
	}
	int query(ii rl, ii rr, int l=0, int r=INF2){
		if(rl.F<=l && r<=rr.F) return val.query(rl.S, rr.S);
		else if(rr.F<l || r<rl.F) return 0;
		else{
			push(l,r);
			int ans=0;
			if(L) ans+=L->query(rl,rr,l,MID);
			if(R) ans+=R->query(rl,rr,MID+1,r);
			return ans;
		}
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin>>n>>q;
	seg2 s;
	seg ss;
	vector<pair<ii,int> > qq;
	vector<pair<ii,int> > dd;
	FOR(i,n){
		int a, b;
		cin>>a>>b;
		dd.push_back({{a,b},a+b});
	}
	while(q--){
		int a, b, c;
		cin>>a>>b>>c;
		qq.push_back({{a,b},c});
	}

	set<int> p1, p2;
	FOA(v,dd) p1.insert(v.F.F);
	FOA(v,dd) p2.insert(v.F.S);
	FOA(v,qq) p1.insert(v.F.F);
	FOA(v,qq) p2.insert(v.F.S);

	map<int, int> m1, m2;
	int cnt=1;
	FOA(v,p1) m1[v] = cnt++;
	cnt=1;
	FOA(v,p2) m2[v] = cnt++;


	FOA(v,dd) s.update({m1[v.F.F], m2[v.F.S]});
	FOA(v,dd) ss.update(v.S);
	FOA(v,qq){
		int ans = s.query({m1[v.F.F], m2[v.F.F]}, {INF, INF});
		if(v.S>v.F.F+v.F.S){
			int inters=0;
			ans -= inters;
		}
		cout<<ans<<endl;
	}
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57