Submission #118165

#	Time	Username	Problem	Language	Result	Execution time	Memory
118165		scanhex	Examination (JOI19_examination)	C++17	100 / 100	927 ms	42160 KiB

examination

#include <bits/stdc++.h>

using namespace std;
using nagai = long long;
#define sz(x) int((x).size())


int act=0;
struct fen{
	vector<int>v;
	vector<int>t;
	void add1(int x,int y){
		for(;x<t.size();x+=x&-x)
			t[x]+=y;
	}
	int get(int x){
		if(act<2)return 0;
		int ans=0;
		for(;x;x-=x&-x)
			ans+=t[x];
		return ans;
	}
	void add(int x,int y){
		if(act<2)
			return v.push_back(x);
		x=lower_bound(v.begin(),v.end(),x)-v.begin();
		add1(x+1,y);
	}
	int get(int l,int r){
		l=lower_bound(v.begin(),v.end(),l)-v.begin();
		r=lower_bound(v.begin(),v.end(),r)-v.begin();
		return get(r)-get(l);
	}
};
const int N=100100;
const int oo=2.1e9;
struct FEN{
	fen kek[N];
	vector<int>v;
	void add1(int x,int y,int z){
		for(;x<N;x+=x&-x)
			kek[x].add(y,z);
	}
	int get(int x,int y1,int y2){
		if(act<2)return 0;
		int ans=0;
		for(;x;x-=x&-x)
			ans+=kek[x].get(y1,y2);
		return ans;
	}
	void add(int x,int y,int z){
		if(act==0)
			return v.push_back(x);
		x=lower_bound(v.begin(),v.end(),x)-v.begin();
		add1(x+1,y,z);
	}
	int get(int x1,int x2,int y1,int y2){
		x1=lower_bound(v.begin(),v.end(),x1)-v.begin();
		x2=lower_bound(v.begin(),v.end(),x2)-v.begin();
		return get(x2,y1,y2)-get(x1,y1,y2);
	}
	void init(){
		if(act==0){
			sort(v.begin(),v.end());
		}
		else{
			for(int i=0;i<N;++i){
				kek[i].v.push_back(oo+5);
				kek[i].v.push_back(oo+5);
				sort(kek[i].v.begin(),kek[i].v.end());
				kek[i].t.resize(kek[i].v.size()+1);
			}
		}
		++act;
	}
} F;

int n,q;
int xs[N],ys[N];
int as[N],bs[N],cs[N];
struct ev{
	int x,y1,y2,z1,z2,id;
	bool operator <(ev o)const {
		if(x!=o.x)
			return x>o.x;
		return id<o.id;
	}
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>q;
	for(int i=0;i<n;++i){
		 cin>>xs[i]>>ys[i];
	}
	for(int i=0;i<q;++i){
		cin>>as[i]>>bs[i]>>cs[i];
	}
	vector<int>ans(q);
	for(int i=0;i<3;++i){
		vector<ev>evs;
		for(int i=0;i<n;++i)
			evs.push_back({xs[i],ys[i],ys[i],xs[i]+ys[i],xs[i]+ys[i],-1});
		for(int i=0;i<q;++i){
			evs.push_back({as[i],bs[i],oo,cs[i],oo,i});
		}
		sort(evs.begin(),evs.end());
		for(auto e:evs){
			if(e.id==-1){
				F.add(e.y1,e.z1,1);
				continue;
			}
			ans[e.id]=F.get(e.y1,e.y2,e.z1,e.z2);
		}
		F.init();
	}
	for(int i=0;i<q;++i)
		cout<<ans[i]<<'\n';
	return 0;
}

Compilation message (stderr)

examination.cpp: In member function 'void fen::add1(int, int)':
examination.cpp:13:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;x<t.size();x+=x&-x)
        ~^~~~~~~~~

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