제출 #630314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
630314		codr0	Examination (JOI19_examination)	C++14	100 / 100	2050 ms	199096 KiB

examination

// Code by Parsa Eslami

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define bit(i,j) ((j>>i)&1)
#define pb push_back
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define err(x) cerr<<#x<<" : "<<x<<'\n'
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1

using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=2e5+4;
const int inf=1e9+1;
ordered_set<pii> seg[4*N];

	void upd(int id,int l,int r,int ind,pii x){
		if(ind>=r||ind<l) return;
		seg[id].insert(x);
		if(l+1==r) return;
		dmid;
		upd(lc,l,mid,ind,x);
		upd(rc,mid,r,ind,x);
	}

	int get(int id,int l,int r,int st,int en,int y){
		if(st>=r||en<=l) return 0;
		if(st<=l&&en>=r) return (seg[id].order_of_key({inf,0})-seg[id].order_of_key({y,0}));
		dmid;
		return (get(lc,l,mid,st,en,y)+get(rc,mid,r,st,en,y));
	}

	int main(){
	iostream::sync_with_stdio(0); cin.tie(0);

	int n,q; cin>>n>>q;
	int a[n+1],b[n+1],c[n+1];
	FOR(i,1,n){ cin>>a[i]>>b[i]; c[i]=a[i]+b[i];}
	int X[q+1],Y[q+1],S[q+1];
	FOR(i,1,q) cin>>X[i]>>Y[i]>>S[i];
	vector<pii> vc;
	FOR(i,1,n) vc.pb({a[i],2*i});
	FOR(i,1,q) vc.pb({X[i],2*i+1});
	sort(all(vc));
	int comp=0;
	FOR(i,0,SZ(vc)-1){
		if(i==0||vc[i].F!=vc[i-1].F) comp++;
		if(vc[i].S&1) X[vc[i].S/2]=comp;
		else a[vc[i].S/2]=comp;
	}
	int ans[q+1]={};
	vector<pii> vc0;
	vector<pii> vc1;
	FOR(i,1,n) vc0.pb({c[i],i});
	FOR(i,1,q) vc1.pb({S[i],i});
	sort(all(vc0)); sort(all(vc1));
	while(!vc1.empty()){
		while(!vc0.empty()&&vc0.back().F>=vc1.back().F){
			int i=vc0.back().S;
			upd(1,1,n+q+1,a[i],{b[i],i});
			vc0.pop_back();
		}
		int i=vc1.back().S;
		ans[i]=get(1,1,n+q+1,X[i],n+q+1,Y[i]);
		vc1.pop_back();
	}
	FOR(i,1,q) cout<<ans[i]<<'\n';

	return 0;
	}

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