Submission #771630

#	Time	Username	Problem	Language	Result	Execution time	Memory
771630		Mohammad_Parsa	Examination (JOI19_examination)	C++17	100 / 100	506 ms	53732 KiB

examination

/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define F first
#define S second
#define mk make_pair
#define ln (e-s+1)
#define md ((s+e)/2)
#define lc (2*id)
#define rc (2*id+1)
typedef long long ll;

const int N=1e5+7;
int n,q,a,b,c,mn[4*N],mx[4*N],ans;
pair<int,int>x[N];
vector<int>v[2][4*N];

void merge(int id,int f){
	int i=0,j=0;
	int sz1=v[f][lc].size(),sz2=v[f][rc].size();
	while(i!=sz1 || j!=sz2){
		if(i==sz1){
			v[f][id].pb(v[f][rc][j++]);
		}
		else if(j==sz2){
			v[f][id].pb(v[f][lc][i++]);
		}
		else{
			if(v[f][lc][i]>v[f][rc][j]){
				v[f][id].pb(v[f][rc][j++]);
			}
			else{
				v[f][id].pb(v[f][lc][i++]);
			}
		}
	}
}

void build(int id=1,int s=1,int e=n){
	if(ln==1){
		mn[id]=mx[id]=x[s].F;
		v[0][id].pb(x[s].F+x[s].S);
		v[1][id].pb(x[s].S);
		return;
	}
	build(lc,s,md);
	build(rc,md+1,e);
	merge(id,0);
	merge(id,1);
	mn[id]=mn[lc];
	mx[id]=mx[rc];
}

void get(int f,int l,int r,int id=1,int s=1,int e=n){
	if(mn[id]>r || l>mx[id])return;
	if(mn[id]>=l && mx[id]<=r){
		int L=-1,R=ln;
		//cout<<id<<endl;
		int w;
		if(f==0)w=c;
		else w=b;
		while(R-L>1){
			int m=(L+R)/2;
			if(v[f][id][m]<w)L=m;
			else R=m;
		}
		//cout<<L<<" "<<R<<endl;
		ans+=ln-R;
		return;
	}
	get(f,l,r,lc,s,md);
	get(f,l,r,rc,md+1,e);
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>x[i].F>>x[i].S;
	}
	sort(x+1,x+n+1);
	build();
	while(q--){
		cin>>a>>b>>c;
		ans=0;
		get(0,a,c-b);
		get(1,max(a,c-b+1),1e9+7);
		cout<<ans<<endl;
	}
}

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