oj.uz

Submission #135531

# Submission time Handle Problem Language Result Execution time Memory
135531 2019-07-24T07:43:08 Z dndhk Examination (JOI19_examination) C++14
43 / 100
 3000 ms 926660 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*400);
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;
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 = tree.size(); tree.pb(tSEG); 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:119: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:200:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vx.size(); i++){
               ~^~~~~~~~~~
examination.cpp:203: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:210: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:212: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:218: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 417 ms 472400 KB Output is correct
2 Correct 404 ms 472504 KB Output is correct
3 Correct 419 ms 472388 KB Output is correct
4 Correct 404 ms 472312 KB Output is correct
5 Correct 430 ms 472316 KB Output is correct
6 Correct 436 ms 472360 KB Output is correct
7 Correct 421 ms 473336 KB Output is correct
8 Correct 426 ms 473464 KB Output is correct
9 Correct 420 ms 473336 KB Output is correct
10 Correct 417 ms 473052 KB Output is correct
11 Correct 450 ms 473080 KB Output is correct
12 Correct 406 ms 472696 KB Output is correct
13 Correct 424 ms 473336 KB Output is correct
14 Correct 442 ms 473464 KB Output is correct
15 Correct 431 ms 473336 KB Output is correct
16 Correct 431 ms 473028 KB Output is correct
17 Correct 429 ms 472972 KB Output is correct
18 Correct 535 ms 472808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2167 ms 489872 KB Output is correct
2 Correct 2253 ms 489888 KB Output is correct
3 Correct 2214 ms 489948 KB Output is correct
4 Correct 918 ms 485156 KB Output is correct
5 Correct 793 ms 483756 KB Output is correct
6 Correct 530 ms 479768 KB Output is correct
7 Correct 2086 ms 488420 KB Output is correct
8 Correct 2061 ms 488912 KB Output is correct
9 Correct 1817 ms 487312 KB Output is correct
10 Correct 655 ms 483308 KB Output is correct
11 Correct 769 ms 484904 KB Output is correct
12 Correct 494 ms 479328 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2167 ms 489872 KB Output is correct
2 Correct 2253 ms 489888 KB Output is correct
3 Correct 2214 ms 489948 KB Output is correct
4 Correct 918 ms 485156 KB Output is correct
5 Correct 793 ms 483756 KB Output is correct
6 Correct 530 ms 479768 KB Output is correct
7 Correct 2086 ms 488420 KB Output is correct
8 Correct 2061 ms 488912 KB Output is correct
9 Correct 1817 ms 487312 KB Output is correct
10 Correct 655 ms 483308 KB Output is correct
11 Correct 769 ms 484904 KB Output is correct
12 Correct 494 ms 479328 KB Output is correct
13 Correct 1986 ms 490304 KB Output is correct
14 Correct 2146 ms 490284 KB Output is correct
15 Correct 2173 ms 489916 KB Output is correct
16 Correct 874 ms 485528 KB Output is correct
17 Correct 743 ms 483836 KB Output is correct
18 Correct 525 ms 479768 KB Output is correct
19 Correct 1924 ms 490308 KB Output is correct
20 Correct 2041 ms 490312 KB Output is correct
21 Correct 1711 ms 489572 KB Output is correct
22 Correct 644 ms 483396 KB Output is correct
23 Correct 750 ms 484980 KB Output is correct
24 Correct 499 ms 479348 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 472400 KB Output is correct
2 Correct 404 ms 472504 KB Output is correct
3 Correct 419 ms 472388 KB Output is correct
4 Correct 404 ms 472312 KB Output is correct
5 Correct 430 ms 472316 KB Output is correct
6 Correct 436 ms 472360 KB Output is correct
7 Correct 421 ms 473336 KB Output is correct
8 Correct 426 ms 473464 KB Output is correct
9 Correct 420 ms 473336 KB Output is correct
10 Correct 417 ms 473052 KB Output is correct
11 Correct 450 ms 473080 KB Output is correct
12 Correct 406 ms 472696 KB Output is correct
13 Correct 424 ms 473336 KB Output is correct
14 Correct 442 ms 473464 KB Output is correct
15 Correct 431 ms 473336 KB Output is correct
16 Correct 431 ms 473028 KB Output is correct
17 Correct 429 ms 472972 KB Output is correct
18 Correct 535 ms 472808 KB Output is correct
19 Correct 2167 ms 489872 KB Output is correct
20 Correct 2253 ms 489888 KB Output is correct
21 Correct 2214 ms 489948 KB Output is correct
22 Correct 918 ms 485156 KB Output is correct
23 Correct 793 ms 483756 KB Output is correct
24 Correct 530 ms 479768 KB Output is correct
25 Correct 2086 ms 488420 KB Output is correct
26 Correct 2061 ms 488912 KB Output is correct
27 Correct 1817 ms 487312 KB Output is correct
28 Correct 655 ms 483308 KB Output is correct
29 Correct 769 ms 484904 KB Output is correct
30 Correct 494 ms 479328 KB Output is correct
31 Correct 1986 ms 490304 KB Output is correct
32 Correct 2146 ms 490284 KB Output is correct
33 Correct 2173 ms 489916 KB Output is correct
34 Correct 874 ms 485528 KB Output is correct
35 Correct 743 ms 483836 KB Output is correct
36 Correct 525 ms 479768 KB Output is correct
37 Correct 1924 ms 490308 KB Output is correct
38 Correct 2041 ms 490312 KB Output is correct
39 Correct 1711 ms 489572 KB Output is correct
40 Correct 644 ms 483396 KB Output is correct
41 Correct 750 ms 484980 KB Output is correct
42 Correct 499 ms 479348 KB Output is correct
43 Execution timed out 3123 ms 926660 KB Time limit exceeded
44 Halted 0 ms 0 KB -