제출 #464072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464072		PixelCat	Examination (JOI19_examination)	C++14	100 / 100	704 ms	55608 KiB

examination

/*    code by the cute PixelCat owo    */
/*     as cute as nyachoneko chan!     */
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
//#define int LL //__int128
#define double long double
using namespace std;
using LL=long long;
using uLL=unsigned long long;
using pii=pair<int,int>;

#define For(i,a,b)    for(int i=a;i<=b;i++)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define Forr(i,a,b)   for(int i=a;i>=b;i--)
#define F first
#define S second
#define L(id) (id*2+1)
#define R(id) (id*2+2)
#define LO(x) (x&(-x))

#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(1000000007)
#define INF (int)(1e17)
#define EPS (1e-6)

#ifdef NYAOWO
	#define debug(...) do{\
		cerr << __LINE__ <<\
		" : ("#__VA_ARGS__ << ") = ";\
		_OUT(__VA_ARGS__);\
		cerr << flush;\
	}while(0)
	template<typename T> void _OUT(T _X) { cerr << _X << "\n"; }
	template<typename T,typename...I>
	void _OUT(T _X,I ...tail) { cerr << _X << ", "; _OUT(tail...); }
	inline void USACO(const string &s) { cerr<<"USACO: "<<s<<"\n"; }
#else
	#define debug(...)
	inline void USACO(const string &s){
		freopen((s+".in").c_str(),"r",stdin);
		freopen((s+".out").c_str(),"w",stdout);
	}
#endif

inline void NYA(){ ios::sync_with_stdio(false); cin.tie(0); }
inline int gcd(int a,int b) { return __gcd(a,b); }
inline int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p,const int &mod){
	int ans=1;
	while(p){
		if(p&1) ans=ans*b%mod;
		p/=2; b=b*b%mod;
	}
	return ans;
}
int fpow(int b,int p) { return fpow(b,p,MOD); }
template<typename T> inline void chmin(T &_a,const T &_b) { if(_b<_a) _a=_b; }
template<typename T> inline void chmax(T &_a,const T &_b) { if(_b>_a) _a=_b; }
template<typename T1,typename T2>
ostream& operator<<(ostream &os,pair<T1,T2> p){
	os<<"("<<p.F<<","<<p.S<<")";
	return os;
}
template<typename T>
ostream& operator<<(ostream &os,const vector<T> &v){
	os<<"[";
	for(auto &i:v)
		os<<" "<<i<<",";
	os<<"]";
	return os;
}
template<typename T>
ostream& operator<<(ostream &os,const deque<T> &v){
	os<<"[";
	for(auto &i:v)
		os<<" "<<i<<",";
	os<<"]";
	return os;
}
template<typename T1,typename T2>
ostream& operator<<(ostream &os,const map<T1,T2> &v){
	os<<"[";
	for(auto &i:v)
		os<<" "<<i.F<<":"<<i.S<<",";
	os<<"]";
	return os;
}
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define MAXN 100000
struct SegTree{
	int l[MAXN*4+10];
	int r[MAXN*4+10];
	vector<int> y[MAXN*4+10];
	void build(int id,vector<pii> &v,int L,int R){
		l[id]=v[L].F;
		r[id]=v[R].F;
		y[id].clear();
		For(i,L,R){
			y[id].eb(v[i].S);
		}
		sort(all(y[id]));
		if(L==R) return;
		int m=(L+R)/2;
		build(L(id),v,L,m);
		build(R(id),v,m+1,R);
	}
	int ask(int id,int L,int R,int Y){
		if(l[id]>R || r[id]<L) return 0;
		if(l[id]>=L && r[id]<=R)
			return sz(y[id])-(lower_bound(all(y[id]),Y)-y[id].begin());
		return ask(L(id),L,R,Y)+ask(R(id),L,R,Y);
	}
}seg1,seg2;

int32_t main(){
	NYA();
	//nyaacho >/////<
	int N,Q; cin>>N>>Q;
	vector<pii> v(N);
	for(auto &i:v)
		cin>>i.F>>i.S;
	sort(all(v));
	seg1.build(0,v,0,N-1);
	for(auto &i:v)
		i.S+=i.F;
	seg2.build(0,v,0,N-1);
	int e9=1000000010;
	while(Q--){
		int x,y,z; cin>>x>>y>>z;
		int x2=max(x,z-y);
		cout<<(seg1.ask(0,x2,e9,y)+seg2.ask(0,x,x2-1,z))<<"\n";
		//cout<<(seg1.ask(0,x2,e9,y))<<" "<<(seg2.ask(0,x,x2-1,z))<<"\n";
	}
	return 0;
}

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