oj.uz

Submission #135558

# Submission time Handle Problem Language Result Execution time Memory
135558 2019-07-24T08:16:57 Z dndhk Examination (JOI19_examination) C++14
100 / 100
 2673 ms 738620 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 709760 KB Output is correct
2 Correct 606 ms 709652 KB Output is correct
3 Correct 605 ms 709644 KB Output is correct
4 Correct 639 ms 709468 KB Output is correct
5 Correct 608 ms 709624 KB Output is correct
6 Correct 605 ms 709624 KB Output is correct
7 Correct 628 ms 710556 KB Output is correct
8 Correct 624 ms 710592 KB Output is correct
9 Correct 628 ms 710628 KB Output is correct
10 Correct 620 ms 710212 KB Output is correct
11 Correct 623 ms 710100 KB Output is correct
12 Correct 613 ms 709872 KB Output is correct
13 Correct 626 ms 710520 KB Output is correct
14 Correct 623 ms 710392 KB Output is correct
15 Correct 630 ms 710492 KB Output is correct
16 Correct 645 ms 710252 KB Output is correct
17 Correct 619 ms 710128 KB Output is correct
18 Correct 607 ms 709760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2410 ms 724100 KB Output is correct
2 Correct 2422 ms 724124 KB Output is correct
3 Correct 2414 ms 724080 KB Output is correct
4 Correct 1081 ms 720288 KB Output is correct
5 Correct 1041 ms 720428 KB Output is correct
6 Correct 756 ms 716952 KB Output is correct
7 Correct 2320 ms 723316 KB Output is correct
8 Correct 2157 ms 723448 KB Output is correct
9 Correct 1981 ms 722580 KB Output is correct
10 Correct 860 ms 720256 KB Output is correct
11 Correct 980 ms 720192 KB Output is correct
12 Correct 684 ms 716520 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2410 ms 724100 KB Output is correct
2 Correct 2422 ms 724124 KB Output is correct
3 Correct 2414 ms 724080 KB Output is correct
4 Correct 1081 ms 720288 KB Output is correct
5 Correct 1041 ms 720428 KB Output is correct
6 Correct 756 ms 716952 KB Output is correct
7 Correct 2320 ms 723316 KB Output is correct
8 Correct 2157 ms 723448 KB Output is correct
9 Correct 1981 ms 722580 KB Output is correct
10 Correct 860 ms 720256 KB Output is correct
11 Correct 980 ms 720192 KB Output is correct
12 Correct 684 ms 716520 KB Output is correct
13 Correct 2112 ms 724264 KB Output is correct
14 Correct 2315 ms 724260 KB Output is correct
15 Correct 2383 ms 724240 KB Output is correct
16 Correct 1042 ms 720400 KB Output is correct
17 Correct 1029 ms 720284 KB Output is correct
18 Correct 779 ms 716924 KB Output is correct
19 Correct 2156 ms 724172 KB Output is correct
20 Correct 2330 ms 724184 KB Output is correct
21 Correct 1861 ms 723476 KB Output is correct
22 Correct 847 ms 720152 KB Output is correct
23 Correct 936 ms 720152 KB Output is correct
24 Correct 685 ms 716472 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 709760 KB Output is correct
2 Correct 606 ms 709652 KB Output is correct
3 Correct 605 ms 709644 KB Output is correct
4 Correct 639 ms 709468 KB Output is correct
5 Correct 608 ms 709624 KB Output is correct
6 Correct 605 ms 709624 KB Output is correct
7 Correct 628 ms 710556 KB Output is correct
8 Correct 624 ms 710592 KB Output is correct
9 Correct 628 ms 710628 KB Output is correct
10 Correct 620 ms 710212 KB Output is correct
11 Correct 623 ms 710100 KB Output is correct
12 Correct 613 ms 709872 KB Output is correct
13 Correct 626 ms 710520 KB Output is correct
14 Correct 623 ms 710392 KB Output is correct
15 Correct 630 ms 710492 KB Output is correct
16 Correct 645 ms 710252 KB Output is correct
17 Correct 619 ms 710128 KB Output is correct
18 Correct 607 ms 709760 KB Output is correct
19 Correct 2410 ms 724100 KB Output is correct
20 Correct 2422 ms 724124 KB Output is correct
21 Correct 2414 ms 724080 KB Output is correct
22 Correct 1081 ms 720288 KB Output is correct
23 Correct 1041 ms 720428 KB Output is correct
24 Correct 756 ms 716952 KB Output is correct
25 Correct 2320 ms 723316 KB Output is correct
26 Correct 2157 ms 723448 KB Output is correct
27 Correct 1981 ms 722580 KB Output is correct
28 Correct 860 ms 720256 KB Output is correct
29 Correct 980 ms 720192 KB Output is correct
30 Correct 684 ms 716520 KB Output is correct
31 Correct 2112 ms 724264 KB Output is correct
32 Correct 2315 ms 724260 KB Output is correct
33 Correct 2383 ms 724240 KB Output is correct
34 Correct 1042 ms 720400 KB Output is correct
35 Correct 1029 ms 720284 KB Output is correct
36 Correct 779 ms 716924 KB Output is correct
37 Correct 2156 ms 724172 KB Output is correct
38 Correct 2330 ms 724184 KB Output is correct
39 Correct 1861 ms 723476 KB Output is correct
40 Correct 847 ms 720152 KB Output is correct
41 Correct 936 ms 720152 KB Output is correct
42 Correct 685 ms 716472 KB Output is correct
43 Correct 2389 ms 738500 KB Output is correct
44 Correct 2462 ms 738620 KB Output is correct
45 Correct 2673 ms 738496 KB Output is correct
46 Correct 1138 ms 727576 KB Output is correct
47 Correct 1052 ms 727544 KB Output is correct
48 Correct 717 ms 716664 KB Output is correct
49 Correct 2596 ms 738480 KB Output is correct
50 Correct 2194 ms 738384 KB Output is correct
51 Correct 2365 ms 738220 KB Output is correct
52 Correct 943 ms 727472 KB Output is correct
53 Correct 1073 ms 726788 KB Output is correct