Submission #126150

#	Time	Username	Problem	Language	Result	Execution time	Memory
126150		dndhk	Examination (JOI19_examination)	C++14	43 / 100	3039 ms	384784 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<S> vt, vt2;

struct SEG{
	struct Node{
		Node(int l, int r, int sum) : l(l), r(r), sum(sum) {}
		int l, r;
		int sum;
	};
	vector<Node> seg;
	void Init(){
		seg.pb({-1, -1, 0});
	}
	void Update(int x){
		//printf("%d\n", x);
		update(0, 0, NY, x);
	}
	void update(int idx, int s, int e, int k){
		while(1){
			seg[idx].sum++;
			if(s==e)	return;
			if(k<=(s+e)/2){
				if(seg[idx].l==-1){
					seg[idx].l = seg.size(); seg.pb({-1, -1, 0});
				}
				idx = seg[idx].l; e = (s+e)/2;
			}else{
				if(seg[idx].r == -1){
					seg[idx].r = seg.size(); seg.pb({-1, -1, 0});
				}
				idx = seg[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({0, 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 += seg[idx].sum;
				continue;
			}
			if(x>e || y<s)	continue;
			vt.pb({seg[idx].l, s, (s+e)/2}); vt.pb({seg[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;
SEG tSEG;

struct SEG2{
	struct Node{
		Node(int l, int r, int num) : l(l), r(r), num(num) {}
		int l, r, num;
	};
	vector<Node> seg;
	int N;
	void Init(){
		N = INF;
		seg.pb({-1, -1, -1});
	}
	vector<int> vt;
	void Update(int x, int y){
		update(0, 0, NX, x);
		for(int i=0; i<vt.size(); i++){
			tree[vt[i]].Update(y);
		}
		vt.clear();
	}
	void update(int idx, int s, int e, int k){
		while(1){
			if(seg[idx].num==-1){
				seg[idx].num = tree.size(); tree.pb(tSEG); tree[seg[idx].num].Init();
			}
			vt.pb(seg[idx].num);
			if(s==e)	return;
			if(k<=(s+e)/2){
				if(seg[idx].l==-1){
					seg[idx].l = seg.size(); seg.pb({-1, -1, -1});
				}
				idx = seg[idx].l; e = (s+e)/2;
			}else{
				if(seg[idx].r == -1){
					seg[idx].r = seg.size(); seg.pb({-1, -1, -1});
				}
				idx = seg[idx].r; s = (s+e)/2+1;
			}
		}
	}
	int Sum(int x, int y, int z, int w){
		vt2.pb({0, 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(seg[idx].num==-1)	continue;
			if(x<=s && e<=y)	{
				ret += tree[seg[idx].num].Sum(z, w);
				continue;
			}
			if(x>e || y<s)	continue;
			vt2.pb({seg[idx].l, s, (s+e)/2}); vt2.pb({seg[idx].r, (s+e)/2+1, e});
		}
		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:114:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<vt.size(); i++){
                ~^~~~~~~~~~
examination.cpp: In function 'void cord()':
examination.cpp:190:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vx.size(); i++){
               ~^~~~~~~~~~
examination.cpp:193: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:200: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:202: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:208: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: 0 / 57