oj.uz

Submission #384311

# Submission time Handle Problem Language Result Execution time Memory
384311 2021-04-01T10:33:12 Z amoo_safar Examination (JOI19_examination) C++17
100 / 100
 847 ms 71928 KB 
// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 998244353;
const int N = 1e5 + 10;
const int Inf = 2000000100;
const ll Log = 30;

typedef pair<int, int> pii;

struct Segment {
	int n = 0;
	vector<pii> V;
	vector<int> seg[N << 2];

	void Add(pii X){
		V.pb(X);
		return ;
	}
	void Build(int id, int L, int R){
		for(int i = L; i < R; i++) seg[id].pb(V[i].S);
		sort(all(seg[id]));
		if(L + 1 == R) return ;
		int mid = (L + R) >> 1;
		Build(id << 1, L, mid);
		Build(id<<1|1, mid, R);
	}
	int Get(int id, int l, int r, int lw, int hg, int L, int R){
		if(r <= L || R <= l) return 0;
		if(l <= L && R <= r){
			return lower_bound(all(seg[id]), hg + 1) - lower_bound(all(seg[id]), lw);
		}
		int mid = (L + R) >> 1;
		return Get(id << 1, l, r, lw, hg, L, mid) + Get(id << 1 | 1, l, r, lw, hg, mid, R);
	}
	int GetRect(int lx, int rx, int ly, int ry){ // [], []
		lx = lower_bound(all(V), pii(lx, -Inf)) - V.begin();
		rx = lower_bound(all(V), pii(rx, Inf)) - V.begin();
		// int sm = 0;
		// for(auto [x, y] : V)
		// 	if(lx <= x && x <= rx && ly <= y && y <= ry) sm ++;
		// return sm;

		return Get(1, lx, rx, ly, ry, 0, n);
	}
	void init(){
		n = V.size();
		sort(all(V));
		Build(1, 0, n);
	}
};
Segment SX, SY, XY;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, q;
	cin >> n >> q;
	int x, y;
	vector<int> U;
	for(int i = 0; i < n; i++){
		cin >> x >> y;
		SX.Add({x + y, x});
		SY.Add({x + y, y});
		XY.Add({x, y});
		U.pb(x + y);
	}
	sort(all(U));
	SX.init();
	SY.init();
	XY.init();

	int a, b, c;
	for(int i = 0; i < q; i++){
		cin >> a >> b >> c;
		if(a + b >= c){
			cout << XY.GetRect(a, Inf, b, Inf) << '\n';
			continue;
		}
		int und = lower_bound(all(U), c) - U.begin();
		int lf = SX.GetRect(c, Inf, 0, a - 1);
		int rt = SY.GetRect(c, Inf, 0, b - 1);
		cout << n - und - lf - rt << '\n';
	}
	return 0;
}
/*
5 1
1 2
2 3
3 4
1 5

*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28524 KB Output is correct
2 Correct 20 ms 28652 KB Output is correct
3 Correct 23 ms 28524 KB Output is correct
4 Correct 22 ms 28524 KB Output is correct
5 Correct 20 ms 28524 KB Output is correct
6 Correct 21 ms 28652 KB Output is correct
7 Correct 33 ms 29676 KB Output is correct
8 Correct 32 ms 29676 KB Output is correct
9 Correct 37 ms 29676 KB Output is correct
10 Correct 30 ms 29676 KB Output is correct
11 Correct 30 ms 29676 KB Output is correct
12 Correct 28 ms 29676 KB Output is correct
13 Correct 31 ms 29676 KB Output is correct
14 Correct 31 ms 29676 KB Output is correct
15 Correct 31 ms 29676 KB Output is correct
16 Correct 27 ms 29676 KB Output is correct
17 Correct 29 ms 29676 KB Output is correct
18 Correct 26 ms 29676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 71300 KB Output is correct
2 Correct 641 ms 71888 KB Output is correct
3 Correct 636 ms 71880 KB Output is correct
4 Correct 558 ms 71652 KB Output is correct
5 Correct 410 ms 71760 KB Output is correct
6 Correct 310 ms 71632 KB Output is correct
7 Correct 597 ms 71632 KB Output is correct
8 Correct 613 ms 71760 KB Output is correct
9 Correct 592 ms 71928 KB Output is correct
10 Correct 293 ms 71504 KB Output is correct
11 Correct 417 ms 71504 KB Output is correct
12 Correct 234 ms 71248 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 71300 KB Output is correct
2 Correct 641 ms 71888 KB Output is correct
3 Correct 636 ms 71880 KB Output is correct
4 Correct 558 ms 71652 KB Output is correct
5 Correct 410 ms 71760 KB Output is correct
6 Correct 310 ms 71632 KB Output is correct
7 Correct 597 ms 71632 KB Output is correct
8 Correct 613 ms 71760 KB Output is correct
9 Correct 592 ms 71928 KB Output is correct
10 Correct 293 ms 71504 KB Output is correct
11 Correct 417 ms 71504 KB Output is correct
12 Correct 234 ms 71248 KB Output is correct
13 Correct 767 ms 71632 KB Output is correct
14 Correct 730 ms 71800 KB Output is correct
15 Correct 661 ms 71760 KB Output is correct
16 Correct 688 ms 71704 KB Output is correct
17 Correct 580 ms 71688 KB Output is correct
18 Correct 333 ms 71632 KB Output is correct
19 Correct 777 ms 71688 KB Output is correct
20 Correct 794 ms 71692 KB Output is correct
21 Correct 793 ms 71676 KB Output is correct
22 Correct 297 ms 71504 KB Output is correct
23 Correct 425 ms 71632 KB Output is correct
24 Correct 243 ms 71248 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28524 KB Output is correct
2 Correct 20 ms 28652 KB Output is correct
3 Correct 23 ms 28524 KB Output is correct
4 Correct 22 ms 28524 KB Output is correct
5 Correct 20 ms 28524 KB Output is correct
6 Correct 21 ms 28652 KB Output is correct
7 Correct 33 ms 29676 KB Output is correct
8 Correct 32 ms 29676 KB Output is correct
9 Correct 37 ms 29676 KB Output is correct
10 Correct 30 ms 29676 KB Output is correct
11 Correct 30 ms 29676 KB Output is correct
12 Correct 28 ms 29676 KB Output is correct
13 Correct 31 ms 29676 KB Output is correct
14 Correct 31 ms 29676 KB Output is correct
15 Correct 31 ms 29676 KB Output is correct
16 Correct 27 ms 29676 KB Output is correct
17 Correct 29 ms 29676 KB Output is correct
18 Correct 26 ms 29676 KB Output is correct
19 Correct 672 ms 71300 KB Output is correct
20 Correct 641 ms 71888 KB Output is correct
21 Correct 636 ms 71880 KB Output is correct
22 Correct 558 ms 71652 KB Output is correct
23 Correct 410 ms 71760 KB Output is correct
24 Correct 310 ms 71632 KB Output is correct
25 Correct 597 ms 71632 KB Output is correct
26 Correct 613 ms 71760 KB Output is correct
27 Correct 592 ms 71928 KB Output is correct
28 Correct 293 ms 71504 KB Output is correct
29 Correct 417 ms 71504 KB Output is correct
30 Correct 234 ms 71248 KB Output is correct
31 Correct 767 ms 71632 KB Output is correct
32 Correct 730 ms 71800 KB Output is correct
33 Correct 661 ms 71760 KB Output is correct
34 Correct 688 ms 71704 KB Output is correct
35 Correct 580 ms 71688 KB Output is correct
36 Correct 333 ms 71632 KB Output is correct
37 Correct 777 ms 71688 KB Output is correct
38 Correct 794 ms 71692 KB Output is correct
39 Correct 793 ms 71676 KB Output is correct
40 Correct 297 ms 71504 KB Output is correct
41 Correct 425 ms 71632 KB Output is correct
42 Correct 243 ms 71248 KB Output is correct
43 Correct 795 ms 71824 KB Output is correct
44 Correct 786 ms 71820 KB Output is correct
45 Correct 734 ms 71732 KB Output is correct
46 Correct 647 ms 71760 KB Output is correct
47 Correct 581 ms 71888 KB Output is correct
48 Correct 311 ms 71504 KB Output is correct
49 Correct 769 ms 71784 KB Output is correct
50 Correct 847 ms 71736 KB Output is correct
51 Correct 793 ms 71760 KB Output is correct
52 Correct 463 ms 71516 KB Output is correct
53 Correct 390 ms 71504 KB Output is correct