oj.uz

Submission #378169

# Submission time Handle Problem Language Result Execution time Memory
378169 2021-03-16T05:57:55 Z cheissmart Examination (JOI19_examination) C++14
100 / 100
 1727 ms 52292 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7, C = 2e9 + 7;

array<int, 4> a[N * 2];
int ans[N];

struct node {
	node *l, *r;
	int val;
	node(int _val = 0) {
		l = r = nullptr;
		val = _val;
	}
};
node* root = nullptr;

void pull(node* t) {
	t -> val = (t -> l ? t -> l -> val : 0) + (t -> r ? t -> r -> val : 0);
}

void add(node*& t, int pos, int val, int tl = 0, int tr = C) {
	if(!t) t = new node();
	if(tr - tl == 1) {
		t -> val += val;
		return;
	}
	int tm = tl + (tr - tl) / 2;
	if(pos < tm) add(t -> l, pos, val, tl, tm);
	else add(t -> r, pos, val, tm, tr);
	pull(t);
}

int qry(node* t, int l, int r, int tl = 0, int tr = C) {
	if(!t) return 0;
	if(l <= tl && tr <= r) return t -> val;
	int tm = tl + (tr - tl) / 2;
	int ans = 0;
	if(l < tm) ans += qry(t -> l, l, r, tl, tm);
	if(r > tm) ans += qry(t -> r, l, r, tm, tr);
	return ans;	
}

void CDQ(int l, int r) {
	if(r - l == 1) return;
	int m = (l + r) / 2;
	CDQ(l, m), CDQ(m, r);
	sort(a + l, a + m, [&] (array<int, 4> x, array<int, 4> y) {
		return x[1] < y[1];
	});
	sort(a + m, a + r, [&] (array<int, 4> x, array<int, 4> y) {
		return x[1] < y[1];
	});
	vi undo;
	for(int i = m - 1, j = r - 1; i >= l; i--) {
		while(j >= m && a[j][1] >= a[i][1]) {
			if(a[j][3] == INF) {
				add(root, a[j][2], 1);
				undo.PB(a[j][2]);
			}
			j--;
		}
		if(a[i][3] != INF)
			ans[a[i][3]] += qry(root, a[i][2], C);		
	} 
	for(int i:undo) add(root, i, -1);
}

signed main()
{
	IO_OP;

	int n, q;
	cin >> n >> q;
	for(int i = 0; i < n; i++) {
		cin >> a[i][0] >> a[i][1];
		a[i][2] = a[i][0] + a[i][1];
		a[i][3] = INF;
	}
	for(int i = n; i < n + q; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2];
		a[i][3] = i - n;
	}
	sort(a, a + n + q);
	CDQ(0, n + q);
	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';

}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 26 ms 2412 KB Output is correct
8 Correct 25 ms 2412 KB Output is correct
9 Correct 26 ms 2412 KB Output is correct
10 Correct 24 ms 2284 KB Output is correct
11 Correct 26 ms 2284 KB Output is correct
12 Correct 17 ms 492 KB Output is correct
13 Correct 24 ms 2412 KB Output is correct
14 Correct 24 ms 2412 KB Output is correct
15 Correct 30 ms 2412 KB Output is correct
16 Correct 22 ms 2412 KB Output is correct
17 Correct 25 ms 2284 KB Output is correct
18 Correct 14 ms 492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 11360 KB Output is correct
2 Correct 1062 ms 11352 KB Output is correct
3 Correct 1037 ms 11460 KB Output is correct
4 Correct 768 ms 9632 KB Output is correct
5 Correct 824 ms 9440 KB Output is correct
6 Correct 558 ms 4600 KB Output is correct
7 Correct 1118 ms 11460 KB Output is correct
8 Correct 1032 ms 11392 KB Output is correct
9 Correct 1076 ms 11484 KB Output is correct
10 Correct 717 ms 9308 KB Output is correct
11 Correct 765 ms 9616 KB Output is correct
12 Correct 520 ms 4276 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1049 ms 11360 KB Output is correct
2 Correct 1062 ms 11352 KB Output is correct
3 Correct 1037 ms 11460 KB Output is correct
4 Correct 768 ms 9632 KB Output is correct
5 Correct 824 ms 9440 KB Output is correct
6 Correct 558 ms 4600 KB Output is correct
7 Correct 1118 ms 11460 KB Output is correct
8 Correct 1032 ms 11392 KB Output is correct
9 Correct 1076 ms 11484 KB Output is correct
10 Correct 717 ms 9308 KB Output is correct
11 Correct 765 ms 9616 KB Output is correct
12 Correct 520 ms 4276 KB Output is correct
13 Correct 1300 ms 11312 KB Output is correct
14 Correct 1322 ms 11412 KB Output is correct
15 Correct 1022 ms 11448 KB Output is correct
16 Correct 981 ms 9856 KB Output is correct
17 Correct 1112 ms 9668 KB Output is correct
18 Correct 735 ms 4572 KB Output is correct
19 Correct 1266 ms 11460 KB Output is correct
20 Correct 1307 ms 11360 KB Output is correct
21 Correct 1282 ms 11444 KB Output is correct
22 Correct 712 ms 9500 KB Output is correct
23 Correct 742 ms 9412 KB Output is correct
24 Correct 520 ms 4260 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 26 ms 2412 KB Output is correct
8 Correct 25 ms 2412 KB Output is correct
9 Correct 26 ms 2412 KB Output is correct
10 Correct 24 ms 2284 KB Output is correct
11 Correct 26 ms 2284 KB Output is correct
12 Correct 17 ms 492 KB Output is correct
13 Correct 24 ms 2412 KB Output is correct
14 Correct 24 ms 2412 KB Output is correct
15 Correct 30 ms 2412 KB Output is correct
16 Correct 22 ms 2412 KB Output is correct
17 Correct 25 ms 2284 KB Output is correct
18 Correct 14 ms 492 KB Output is correct
19 Correct 1049 ms 11360 KB Output is correct
20 Correct 1062 ms 11352 KB Output is correct
21 Correct 1037 ms 11460 KB Output is correct
22 Correct 768 ms 9632 KB Output is correct
23 Correct 824 ms 9440 KB Output is correct
24 Correct 558 ms 4600 KB Output is correct
25 Correct 1118 ms 11460 KB Output is correct
26 Correct 1032 ms 11392 KB Output is correct
27 Correct 1076 ms 11484 KB Output is correct
28 Correct 717 ms 9308 KB Output is correct
29 Correct 765 ms 9616 KB Output is correct
30 Correct 520 ms 4276 KB Output is correct
31 Correct 1300 ms 11312 KB Output is correct
32 Correct 1322 ms 11412 KB Output is correct
33 Correct 1022 ms 11448 KB Output is correct
34 Correct 981 ms 9856 KB Output is correct
35 Correct 1112 ms 9668 KB Output is correct
36 Correct 735 ms 4572 KB Output is correct
37 Correct 1266 ms 11460 KB Output is correct
38 Correct 1307 ms 11360 KB Output is correct
39 Correct 1282 ms 11444 KB Output is correct
40 Correct 712 ms 9500 KB Output is correct
41 Correct 742 ms 9412 KB Output is correct
42 Correct 520 ms 4260 KB Output is correct
43 Correct 1670 ms 52188 KB Output is correct
44 Correct 1649 ms 52292 KB Output is correct
45 Correct 1660 ms 52036 KB Output is correct
46 Correct 1311 ms 49988 KB Output is correct
47 Correct 1500 ms 49988 KB Output is correct
48 Correct 724 ms 4320 KB Output is correct
49 Correct 1727 ms 52164 KB Output is correct
50 Correct 1672 ms 52156 KB Output is correct
51 Correct 1659 ms 52048 KB Output is correct
52 Correct 1268 ms 49564 KB Output is correct
53 Correct 1006 ms 49860 KB Output is correct