oj.uz

Submission #126146

# Submission time Handle Problem Language Result Execution time Memory
126146 2019-07-07T06:03:49 Z dndhk Examination (JOI19_examination) C++14
41 / 100
 2113 ms 286028 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 100000
#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;



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, INF, 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, INF});
		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, N, 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, N});
		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;
	}
};

vector<S> v;
vector<Query> query;
int ans[MAX_N+1];

int main(){
	scanf("%d%d", &M, &Q);
	for(int i=0; i<M; i++){
		int a, b; scanf("%d%d", &a, &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);
		query.pb({c, a, b, i});
	}
	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(now.b, INF, now.c, INF);
			//cout<<endl;
		}else{
			S now = v.back(); v.pop_back();
			//cout<<now.a<<" "<<now.b<<" "<<now.c<<endl<<"======================="<<endl;
			Seg.Update(now.b, 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:113:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<vt.size(); i++){
                ~^~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:185: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:187: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:192: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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2094 ms 282116 KB Output is correct
2 Correct 2101 ms 284120 KB Output is correct
3 Correct 2079 ms 284640 KB Output is correct
4 Correct 840 ms 76928 KB Output is correct
5 Correct 589 ms 59068 KB Output is correct
6 Correct 351 ms 6144 KB Output is correct
7 Correct 2021 ms 284488 KB Output is correct
8 Correct 1962 ms 284380 KB Output is correct
9 Correct 1888 ms 283788 KB Output is correct
10 Correct 441 ms 44428 KB Output is correct
11 Correct 671 ms 72780 KB Output is correct
12 Correct 274 ms 5828 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2094 ms 282116 KB Output is correct
2 Correct 2101 ms 284120 KB Output is correct
3 Correct 2079 ms 284640 KB Output is correct
4 Correct 840 ms 76928 KB Output is correct
5 Correct 589 ms 59068 KB Output is correct
6 Correct 351 ms 6144 KB Output is correct
7 Correct 2021 ms 284488 KB Output is correct
8 Correct 1962 ms 284380 KB Output is correct
9 Correct 1888 ms 283788 KB Output is correct
10 Correct 441 ms 44428 KB Output is correct
11 Correct 671 ms 72780 KB Output is correct
12 Correct 274 ms 5828 KB Output is correct
13 Correct 1861 ms 284816 KB Output is correct
14 Correct 2104 ms 285064 KB Output is correct
15 Correct 2113 ms 285216 KB Output is correct
16 Correct 663 ms 77400 KB Output is correct
17 Correct 548 ms 59792 KB Output is correct
18 Correct 358 ms 6192 KB Output is correct
19 Correct 1820 ms 284860 KB Output is correct
20 Correct 1983 ms 286028 KB Output is correct
21 Correct 1737 ms 284764 KB Output is correct
22 Correct 445 ms 44624 KB Output is correct
23 Correct 668 ms 72524 KB Output is correct
24 Correct 274 ms 5856 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -