Submission #135558

#	Time	Username	Problem	Language	Result	Execution time	Memory
135558		dndhk	Examination (JOI19_examination)	C++14	100 / 100	2673 ms	738620 KiB

examination

#include <bits/stdc++.h>
 
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 1000000000
#define INFLL 1000000000000000000LL
 
const int MAX_N = 100000;
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int NX, NY;
 
 
struct S{
	S(int a, int b, int c) : a(a), b(b), c(c) {}
	int a, b, c;
	bool operator <(const S &t)const{
		return a<t.a;
	}
};

vector<int> vct;
vector<S> vt, vt2;
struct Node1{
	int l=-1, r=-1;
	int sum=0;
};

vector<Node1> seg1(MAX_N*600);
int cnt1 = 0;

struct SEG{
	int r;
	void Init(){
		r = cnt1++;
	}
	void Update(int x){
		//printf("%d\n", x);
		update(r, 0, NY, x);
	}
	void update(int idx, int s, int e, int k){
		while(1){
			seg1[idx].sum++;
			if(s==e)	return;
			if(k<=(s+e)/2){
				if(seg1[idx].l==-1){
					seg1[idx].l = cnt1++;
				}
				idx = seg1[idx].l; e = (s+e)/2;
			}else{
				if(seg1[idx].r == -1){
					seg1[idx].r = cnt1++;
				}
				idx = seg1[idx].r; s = (s+e)/2+1;
			}
		}
	}
	int Sum(int x, int y){
		//cout<<x<<" "<<y<<endl;
		int ret = 0;
		int idx, s, e;
		vt.pb({r, 0, NY});
		while(!vt.empty()){
			idx = vt.back().a; s = vt.back().b; e = vt.back().c; vt.pop_back();
			if(idx==-1)	continue;
			if(x<=s && e<=y){
				ret += seg1[idx].sum;
				continue;
			}
			if(x>e || y<s)	continue;
			vt.pb({seg1[idx].l, s, (s+e)/2}); vt.pb({seg1[idx].r, (s+e)/2+1, e});
		}
		return ret;
	}/*
	int sum(int idx, int s, int e, int x, int y){
		if(x==-1)	return 0;
		if(x<=s && e<=y)	{
			//if(seg[idx].sum!=0)	cout<<s<<" "<<e<<" "<<seg[idx].sum<<endl;
			return seg[idx].sum;
		}
		if(x>e || y<s)	return 0;
		return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
	}*/
};
 
vector<SEG> tree(MAX_N*3);
int cnt = 0;
SEG tSEG;

struct Node2{
	int l=-1, r=-1, num=-1;
};

vector<Node2> seg2(MAX_N*3);
int cnt2 = 0;

struct SEG2{
	int r;
	int N;
	void Init(){
		N = INF;
		r = cnt2++;
	}
	void Update(int x, int y){
		update(r, 0, NX, x);
		for(int i=0; i<vct.size(); i++){
			tree[vct[i]].Update(y);
		}
		while(!vct.empty())	vct.pop_back();
	}
	void update(int idx, int s, int e, int k){
		while(1){
			if(seg2[idx].num==-1){
				seg2[idx].num = cnt++; tree[seg2[idx].num].Init();
			}
			vct.pb(seg2[idx].num);
			if(s==e)	return;
			if(k<=(s+e)/2){
				if(seg2[idx].l==-1){
					seg2[idx].l = cnt2++;
				}
				idx = seg2[idx].l; e = (s+e)/2;
			}else{
				if(seg2[idx].r == -1){
					seg2[idx].r = cnt2++;
				}
				idx = seg2[idx].r; s = (s+e)/2+1;
			}
		}
	}
	int Sum(int x, int y, int z, int w){
		vt2.pb({r, 0, NX});
		int ret=0;
		int idx, s, e;
		while(!vt2.empty()){
			idx = vt2.back().a; s = vt2.back().b; e = vt2.back().c;	vt2.pop_back();
			if(idx==-1)	continue;
			if(seg2[idx].num==-1)	continue;
			if(x<=s && e<=y)	{
				vct.pb(seg2[idx].num);
				//ret += tree[seg[idx].num].Sum(z, w);
				continue;
			}
			if(x>e || y<s)	continue;
			vt2.pb({seg2[idx].l, s, (s+e)/2}); vt2.pb({seg2[idx].r, (s+e)/2+1, e});
		}
		while(!vct.empty()){
			ret += tree[vct.back()].Sum(z, w);
			vct.pop_back();
		}
		return ret;
	}
	/*
	int sum(int idx, int s, int e, int x, int y, int z, int w){
		if(idx==-1)	return 0;
		if(seg[idx].num==-1)	return 0;
		if(x<=s && e<=y){
			//cout<<s<<" "<<e<<" "<<z<<" "<<w<<" "<<tree[seg[idx].num].Sum(z, w)<<endl;
			return tree[seg[idx].num].Sum(z, w);
		}
		if(x>e || y<s)	return 0;
		return sum(seg[idx].l, s, (s+e)/2, x, y, z, w) + sum(seg[idx].r, (s+e)/2+1, e, x, y, z, w);
	}*/
};
 
SEG2 Seg;
 
int M, Q;
struct Query{
	Query(int a, int b, int c, int idx) : a(a), b(b), c(c), idx(idx) {}
	int a, b, c;
	int idx;
	bool operator <(const Query &t)const{
		return a<t.a;
	}
};
 
map<int, int> X, Y;
vector<int> vx, vy;
vector<S> v;
vector<Query> query;
int ans[MAX_N+1];
 
void cord(){
	sort(vx.begin(), vx.end()); sort(vy.begin(), vy.end());
	vx.erase(unique(vx.begin(), vx.end()), vx.end()); vy.erase(unique(vy.begin(), vy.end()), vy.end());
	for(int i=0; i<vx.size(); i++){
		X[vx[i]] = i;
	}
	for(int i=0; i<vy.size(); i++){
		Y[vy[i]] = i;
	}
	NX = vx.size()-1; NY = vy.size()-1;
}
 
int main(){
	scanf("%d%d", &M, &Q);
	for(int i=0; i<M; i++){
		int a, b; scanf("%d%d", &a, &b);
		vx.pb(a); vy.pb(b);
		v.pb({a+b, a, b});
	}
	for(int i=0; i<Q; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		vx.pb(a); vy.pb(b);
		query.pb({c, a, b, i});
	}
	cord();
	sort(v.begin(), v.end());
	sort(query.begin(), query.end());
	Seg.Init();
	while(!query.empty()){
		if(v.empty() || query.back().a > v.back().a){
			Query now = query.back(); query.pop_back();
			ans[now.idx] = Seg.Sum(X[now.b], NX, Y[now.c], NY);
			//cout<<endl;
		}else{
			S now = v.back(); v.pop_back();
			//cout<<now.a<<" "<<now.b<<" "<<now.c<<endl<<"======================="<<endl;
			Seg.Update(X[now.b], Y[now.c]);
		}	
	}
	for(int i=0; i<Q; i++){
		printf("%d\n", ans[i]);
	}
 
	return 0;
}

Compilation message (stderr)

examination.cpp: In member function 'void SEG2::Update(int, int)':
examination.cpp:120:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<vct.size(); i++){
                ~^~~~~~~~~~~
examination.cpp: In function 'void cord()':
examination.cpp:201:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vx.size(); i++){
               ~^~~~~~~~~~
examination.cpp:204:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vy.size(); i++){
               ~^~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:211:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &M, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:213:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:219:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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