Submission #209064

#	Time	Username	Problem	Language	Result	Execution time	Memory
209064		YJU	Examination (JOI19_examination)	C++14	100 / 100	649 ms	19376 KiB

examination

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<pll,pll> tyty;
const ll N=1e6+5;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define lwb lower_bound
#define Y second
#define SZ(a) (ll)a.size()

ll bit[N],n,q,s,t,a,b,c,ans[N];
vector<tyty> v;
vector<ll> lis;

void add(ll id,ll d){
	while(id<N)bit[id]+=d,id+=(id&-id);
}

ll Q(ll id){
	ll tmp=0;
	while(id)tmp+=bit[id],id-=(id&-id);
	return tmp;
}

void CDQ(ll l,ll r){
	//cout<<l<<" "<<r<<"\n";
	if(r==l+1)return;
	ll mid=(l+r)/2;
	CDQ(l,mid);CDQ(mid,r);
	ll ql=l,qr=mid;
	vector<ll> que;
	while(ql<mid&&qr<r){
		if(v[ql].X.Y<=v[qr].X.Y){
			if(v[ql].Y.Y==0)add(v[ql].Y.X,1),que.pb(v[ql].Y.X);
			++ql;
		}else{
			if(v[qr].Y.Y!=0)ans[v[qr].Y.Y]+=Q(v[qr].Y.X);
			++qr;
		}
	}
	//while(ql<mid)
	while(qr<r)if(v[qr].Y.Y!=0)ans[v[qr].Y.Y]+=Q(v[qr].Y.X),++qr;else ++qr;
	for(ll i:que){add(i,-1);}
	sort(v.begin()+l,v.begin()+r,[](tyty a,tyty b){return (a.X.Y!=b.X.Y?a.X.Y<b.X.Y:a.Y.Y<b.Y.Y);});
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>q;
	REP(i,n)cin>>s>>t,v.pb(mp(mp(-s,-t),mp(-(s+t),0))),lis.pb(-s),lis.pb(-t),lis.pb(-s-t);
	REP1(i,q)cin>>a>>b>>c,v.pb(mp(mp(-a,-b),mp(-c,i))),lis.pb(-a),lis.pb(-b),lis.pb(-c);
	sort(lis.begin(),lis.end());
	lis.resize(unique(lis.begin(),lis.end())-lis.begin());
	for(auto &i:v){
		i.X.X=lwb(lis.begin(),lis.end(),i.X.X)-lis.begin()+1;
		i.X.Y=lwb(lis.begin(),lis.end(),i.X.Y)-lis.begin()+1;
		i.Y.X=lwb(lis.begin(),lis.end(),i.Y.X)-lis.begin()+1;
	}
	sort(v.begin(),v.end());
	CDQ(0,SZ(v));
	REP1(i,q)cout<<ans[i]<<"\n";
	return 0;
}

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