Submission #1281880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281880		hanguyendanghuy	Examination (JOI19_examination)	C++20	100 / 100	226 ms	20812 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
const ll MAXN=4e5+5,INF=1e9,MOD=1e9+7,MAXV=4e5+2;
ll n,m,i,j,k,p,dem,cnta[MAXN],cntb[MAXN],cntval[MAXN],ans[MAXN];
struct h{
	ll a,b,c,id,f;
} a[MAXN],q[MAXN];
bool cmp(h x,h y){
	return x.a<y.a;
}
bool cmp1(h x,h y){
	return x.b<y.b;
}
struct fen{
	ll b[MAXN];
	void update(ll pos,ll val){
		while(pos<MAXV){
			b[pos]+=val;
			pos+=pos&-pos;
		}
	}
	ll get(ll pos){
		ll ans=0;
		while(pos>0){
			ans+=b[pos];
			pos-=pos&-pos;
		}
		return ans;
	}
} fena,fenb,fenc,fenval,fen;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	vector<ll> vala,valb,valc;
	for(i=1;i<=n;i++){
	  cin>>a[i].a>>a[i].b;
	  a[i].c=a[i].a+a[i].b;
	  vala.pb(a[i].a);
	  valb.pb(a[i].b);
	  valc.pb(a[i].c);
	}
	for(i=1;i<=m;i++){
	  cin>>q[i].a>>q[i].b>>q[i].c;
	  q[i].id=i;
	  if(q[i].a+q[i].b<q[i].c) q[i].f=1;
	  vala.pb(q[i].a);
	  valb.pb(q[i].b);
	  valc.pb(q[i].c);
	}
	sort(vala.begin(),vala.end());
	sort(valb.begin(),valb.end());
	sort(valc.begin(),valc.end());
	vala.resize(unique(vala.begin(),vala.end())-vala.begin());
	valb.resize(unique(valb.begin(),valb.end())-valb.begin());
	valc.resize(unique(valc.begin(),valc.end())-valc.begin());
	for(i=1;i<=n;i++){
	  a[i].a=lower_bound(vala.begin(),vala.end(),a[i].a)-vala.begin()+1;
	  a[i].b=lower_bound(valb.begin(),valb.end(),a[i].b)-valb.begin()+1;
	  a[i].c=lower_bound(valc.begin(),valc.end(),a[i].c)-valc.begin()+1;
	}
	for(i=1;i<=m;i++){
	  q[i].a=lower_bound(vala.begin(),vala.end(),q[i].a)-vala.begin()+1;
	  q[i].b=lower_bound(valb.begin(),valb.end(),q[i].b)-valb.begin()+1;
	  q[i].c=lower_bound(valc.begin(),valc.end(),q[i].c)-valc.begin()+1;
	}
	sort(a+1,a+n+1,cmp1);
	sort(q+1,q+m+1,cmp1);	
	ll cur=n;
	for(i=1;i<=n;i++)
		fenc.update(a[i].c,1);
	for(i=m;i>=1;i--){
		while(cur>0&&a[cur].b>=q[i].b){
			fenc.update(a[cur].c,-1);
			cur--;
		}
		if(q[i].f)
		  ans[q[i].id]=-fenc.get(q[i].c-1);
	}
	sort(a+1,a+n+1,cmp);
	sort(q+1,q+m+1,cmp);	
	for(i=1;i<=n;i++){
		fenb.update(a[i].b,1);
	}
	cur=n;
	for(i=m;i>=1;i--){
		while(cur>0&&a[cur].a>=q[i].a){
			fenb.update(a[cur].b,-1);
			fenval.update(a[cur].c,1);
			fen.update(MAXV-a[cur].b,1);
			cur--;
		}
		if(q[i].f)
		  ans[q[i].id]+=fenb.get(q[i].b-1)+fenval.get(q[i].c-1);
		ans[q[i].id]=fen.get(MAXV-q[i].b)-max(0ll,ans[q[i].id]);
	}
	for(i=1;i<=m;i++)
		cout<<ans[i]<<'\n';
}
	

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