oj.uz

Submission #135556

# Submission time Handle Problem Language Result Execution time Memory
135556 2019-07-24T08:14:58 Z dndhk Examination (JOI19_examination) C++14
43 / 100
 2388 ms 1048576 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*500);
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*2);
int cnt = 0;
SEG tSEG;

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

vector<Node2> seg2(MAX_N*2);
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 510 ms 590484 KB Output is correct
2 Correct 508 ms 590740 KB Output is correct
3 Correct 521 ms 590596 KB Output is correct
4 Correct 526 ms 590808 KB Output is correct
5 Correct 566 ms 590712 KB Output is correct
6 Correct 508 ms 590580 KB Output is correct
7 Correct 529 ms 591436 KB Output is correct
8 Correct 563 ms 591480 KB Output is correct
9 Correct 524 ms 591488 KB Output is correct
10 Correct 518 ms 591096 KB Output is correct
11 Correct 531 ms 591096 KB Output is correct
12 Correct 519 ms 590948 KB Output is correct
13 Correct 530 ms 591432 KB Output is correct
14 Correct 528 ms 591576 KB Output is correct
15 Correct 532 ms 591460 KB Output is correct
16 Correct 524 ms 591224 KB Output is correct
17 Correct 528 ms 591240 KB Output is correct
18 Correct 511 ms 590812 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2350 ms 606372 KB Output is correct
2 Correct 2388 ms 606488 KB Output is correct
3 Correct 2309 ms 606380 KB Output is correct
4 Correct 984 ms 601680 KB Output is correct
5 Correct 916 ms 601568 KB Output is correct
6 Correct 630 ms 597964 KB Output is correct
7 Correct 2313 ms 605400 KB Output is correct
8 Correct 2154 ms 605488 KB Output is correct
9 Correct 1877 ms 604792 KB Output is correct
10 Correct 754 ms 601752 KB Output is correct
11 Correct 857 ms 601624 KB Output is correct
12 Correct 588 ms 597528 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2350 ms 606372 KB Output is correct
2 Correct 2388 ms 606488 KB Output is correct
3 Correct 2309 ms 606380 KB Output is correct
4 Correct 984 ms 601680 KB Output is correct
5 Correct 916 ms 601568 KB Output is correct
6 Correct 630 ms 597964 KB Output is correct
7 Correct 2313 ms 605400 KB Output is correct
8 Correct 2154 ms 605488 KB Output is correct
9 Correct 1877 ms 604792 KB Output is correct
10 Correct 754 ms 601752 KB Output is correct
11 Correct 857 ms 601624 KB Output is correct
12 Correct 588 ms 597528 KB Output is correct
13 Correct 2035 ms 606816 KB Output is correct
14 Correct 2348 ms 606888 KB Output is correct
15 Correct 2302 ms 606636 KB Output is correct
16 Correct 939 ms 602048 KB Output is correct
17 Correct 878 ms 602060 KB Output is correct
18 Correct 638 ms 597996 KB Output is correct
19 Correct 2045 ms 606812 KB Output is correct
20 Correct 2132 ms 606772 KB Output is correct
21 Correct 1774 ms 606016 KB Output is correct
22 Correct 793 ms 601468 KB Output is correct
23 Correct 846 ms 601632 KB Output is correct
24 Correct 587 ms 597492 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 590484 KB Output is correct
2 Correct 508 ms 590740 KB Output is correct
3 Correct 521 ms 590596 KB Output is correct
4 Correct 526 ms 590808 KB Output is correct
5 Correct 566 ms 590712 KB Output is correct
6 Correct 508 ms 590580 KB Output is correct
7 Correct 529 ms 591436 KB Output is correct
8 Correct 563 ms 591480 KB Output is correct
9 Correct 524 ms 591488 KB Output is correct
10 Correct 518 ms 591096 KB Output is correct
11 Correct 531 ms 591096 KB Output is correct
12 Correct 519 ms 590948 KB Output is correct
13 Correct 530 ms 591432 KB Output is correct
14 Correct 528 ms 591576 KB Output is correct
15 Correct 532 ms 591460 KB Output is correct
16 Correct 524 ms 591224 KB Output is correct
17 Correct 528 ms 591240 KB Output is correct
18 Correct 511 ms 590812 KB Output is correct
19 Correct 2350 ms 606372 KB Output is correct
20 Correct 2388 ms 606488 KB Output is correct
21 Correct 2309 ms 606380 KB Output is correct
22 Correct 984 ms 601680 KB Output is correct
23 Correct 916 ms 601568 KB Output is correct
24 Correct 630 ms 597964 KB Output is correct
25 Correct 2313 ms 605400 KB Output is correct
26 Correct 2154 ms 605488 KB Output is correct
27 Correct 1877 ms 604792 KB Output is correct
28 Correct 754 ms 601752 KB Output is correct
29 Correct 857 ms 601624 KB Output is correct
30 Correct 588 ms 597528 KB Output is correct
31 Correct 2035 ms 606816 KB Output is correct
32 Correct 2348 ms 606888 KB Output is correct
33 Correct 2302 ms 606636 KB Output is correct
34 Correct 939 ms 602048 KB Output is correct
35 Correct 878 ms 602060 KB Output is correct
36 Correct 638 ms 597996 KB Output is correct
37 Correct 2045 ms 606812 KB Output is correct
38 Correct 2132 ms 606772 KB Output is correct
39 Correct 1774 ms 606016 KB Output is correct
40 Correct 793 ms 601468 KB Output is correct
41 Correct 846 ms 601632 KB Output is correct
42 Correct 587 ms 597492 KB Output is correct
43 Runtime error 2228 ms 1048576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -