Submission #118155

#	Time	Username	Problem	Language	Result	Execution time	Memory
118155		scanhex	Examination (JOI19_examination)	C++17	0 / 100	592 ms	34172 KiB

examination

#include <bits/stdc++.h>

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


bool act=false;
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)return 0;
		int ans=0;
		for(;x;x-=x&-x)
			ans+=t[x];
		return ans;
	}
	void add(int x,int y){
		if(!act)
			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=0x3f3f3f3f;
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){
		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)
//			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(){
		//sort(v.begin(),v.end());
		for(int i=0;i<N;++i){
			kek[i].v.push_back(1e9);
			sort(kek[i].v.begin(),kek[i].v.end());
			kek[i].t.resize(kek[i].v.size()+1);
		}
		act=true;
	}
} 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<2;++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],N-3,cs[i],N-3,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: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57