oj.uz

Submission #206764

# Submission time Handle Problem Language Result Execution time Memory
206764 2020-03-05T07:01:47 Z Neklixx Examination (JOI19_examination) C++14
100 / 100
 2511 ms 374376 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define sh cin.tie(0); cin.sync_with_stdio(0); cout.tie(0);
#define FILE freopen("test.in", "r", stdin);
#define vprint(v) for (int ii = 0; ii < v.size(); ii++){cout << v[ii] << " ";}
#define debugv(v) if (v.size() != 0) {cout << "[ "; for (int __ = 0; __ < (int)(v.size()) - 1; __++){cout << v[__] << ", ";} cout << v[(int)(v.size()) - 1] << " ]" << endl;} else {cout << "[]" << endl;}
#define debug cout << "-----------------------------------------------" << endl;
#define print1(a) cout << "{ " << a << " }" << endl;
#define print2(a, b) cout << "{ " << a << ", " << b << " }" << endl;
#define print3(a, b, c) cout << "{ " << a << ", " << b << ", " << c << " }" << endl;
#define print4(a, b, c, d) cout << "{ " << a << ", " << b << ", " << c << ", " << d << " }" << endl;
using namespace std;
//#define int long long
const int INF = 2e9 + 228;
const int MAXN = 1e5 + 228;
vector<pair<pair<int, int>, int>> a;
vector<pair<int, int>> t[MAXN * 4];

vector<vector<int>> t1[MAXN * 4];

void build1(int l, int r, int v, int id) {
	for (int i = l; i <= r; i++) {
		t1[id][v].pb(t[id][i].S);
	}
	sort(all(t1[id][v]));
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	build1(l, mid, v * 2, id);
	build1(mid + 1, r, v * 2 + 1, id);
}

void build(int l, int r, int v) {
	for (int i = l; i <= r; i++) {
		t[v].pb({a[i].F.S, a[i].S});
	}
	sort(all(t[v]));
	t1[v].resize(4 * t[v].size());
	build1(0, t[v].size() - 1, 1, v);
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid, 2 * v);
	build(mid + 1, r, v * 2 + 1);
}

int get1(int v, int l, int r, int tl, int tr, int z, int v1) {
	if (tl > tr)
		return 0;
	if (tl == l && tr == r) {
		int id = lower_bound(all(t1[v1][v]), z) - t1[v1][v].begin();
		return t1[v1][v].size() - id;
	}
	int mid = (l + r) / 2;
	return 	get1(v * 2, l, mid, tl, min(tr, mid), z, v1) + 
			get1(v * 2 + 1, mid + 1, r, max(tl, mid + 1), tr, z, v1);
}

int get(int v, int l, int r, int tl, int tr, int y, int z) {
	if (tl > tr)
		return 0;
	if (tl == l && tr == r) {
		int id = lower_bound(all(t[v]), mp(y, -INF)) - t[v].begin();
		return get1(1, 0, t[v].size() - 1, id, t[v].size() - 1, z, v);
	}
	int mid = (l + r) / 2;
	return 	get(v * 2, l, mid, tl, min(tr, mid), y, z) + 
			get(v * 2 + 1, mid + 1, r, max(tl, mid + 1), tr, y, z);
}

signed main()
{
#ifdef LOCAL
    FILE;
#endif
    sh;
	int n;
	cin >> n;
	int q;
	cin >> q;
	//print1("sorted");
	for (int i = 0; i < n; i++) {
		int aa, bb;
		cin >> aa >> bb;
		a.pb({{aa, bb}, aa + bb});
	}
	sort(all(a));
	build(0, n - 1, 1);
	//print1("built");
	for (int _ = 0; _ < q; _++) {
		int x, y, z;
		cin >> x >> y >> z;
		int id = lower_bound(all(a), mp(mp(x, -INF), -INF)) - a.begin();
		int now = get(1, 0, n - 1, id, n - 1, y, z);
		cout << now << endl;
	}
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19192 KB Output is correct
2 Correct 17 ms 19192 KB Output is correct
3 Correct 17 ms 19192 KB Output is correct
4 Correct 17 ms 19192 KB Output is correct
5 Correct 17 ms 19192 KB Output is correct
6 Correct 16 ms 19196 KB Output is correct
7 Correct 52 ms 26488 KB Output is correct
8 Correct 53 ms 26488 KB Output is correct
9 Correct 52 ms 26488 KB Output is correct
10 Correct 51 ms 26360 KB Output is correct
11 Correct 48 ms 26488 KB Output is correct
12 Correct 45 ms 26360 KB Output is correct
13 Correct 54 ms 26488 KB Output is correct
14 Correct 54 ms 26616 KB Output is correct
15 Correct 53 ms 26488 KB Output is correct
16 Correct 43 ms 26360 KB Output is correct
17 Correct 46 ms 26488 KB Output is correct
18 Correct 43 ms 26360 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2388 ms 371768 KB Output is correct
2 Correct 2319 ms 371816 KB Output is correct
3 Correct 2372 ms 371688 KB Output is correct
4 Correct 2105 ms 370944 KB Output is correct
5 Correct 1573 ms 371112 KB Output is correct
6 Correct 1390 ms 370280 KB Output is correct
7 Correct 2226 ms 371632 KB Output is correct
8 Correct 2169 ms 371684 KB Output is correct
9 Correct 2052 ms 371508 KB Output is correct
10 Correct 1399 ms 370896 KB Output is correct
11 Correct 1500 ms 370920 KB Output is correct
12 Correct 1268 ms 369940 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2388 ms 371768 KB Output is correct
2 Correct 2319 ms 371816 KB Output is correct
3 Correct 2372 ms 371688 KB Output is correct
4 Correct 2105 ms 370944 KB Output is correct
5 Correct 1573 ms 371112 KB Output is correct
6 Correct 1390 ms 370280 KB Output is correct
7 Correct 2226 ms 371632 KB Output is correct
8 Correct 2169 ms 371684 KB Output is correct
9 Correct 2052 ms 371508 KB Output is correct
10 Correct 1399 ms 370896 KB Output is correct
11 Correct 1500 ms 370920 KB Output is correct
12 Correct 1268 ms 369940 KB Output is correct
13 Correct 2459 ms 372076 KB Output is correct
14 Correct 2511 ms 372340 KB Output is correct
15 Correct 2411 ms 371840 KB Output is correct
16 Correct 2245 ms 371432 KB Output is correct
17 Correct 1658 ms 371304 KB Output is correct
18 Correct 1435 ms 370392 KB Output is correct
19 Correct 2425 ms 372284 KB Output is correct
20 Correct 2433 ms 372360 KB Output is correct
21 Correct 2389 ms 372412 KB Output is correct
22 Correct 1411 ms 370792 KB Output is correct
23 Correct 1489 ms 370868 KB Output is correct
24 Correct 1267 ms 369752 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19192 KB Output is correct
2 Correct 17 ms 19192 KB Output is correct
3 Correct 17 ms 19192 KB Output is correct
4 Correct 17 ms 19192 KB Output is correct
5 Correct 17 ms 19192 KB Output is correct
6 Correct 16 ms 19196 KB Output is correct
7 Correct 52 ms 26488 KB Output is correct
8 Correct 53 ms 26488 KB Output is correct
9 Correct 52 ms 26488 KB Output is correct
10 Correct 51 ms 26360 KB Output is correct
11 Correct 48 ms 26488 KB Output is correct
12 Correct 45 ms 26360 KB Output is correct
13 Correct 54 ms 26488 KB Output is correct
14 Correct 54 ms 26616 KB Output is correct
15 Correct 53 ms 26488 KB Output is correct
16 Correct 43 ms 26360 KB Output is correct
17 Correct 46 ms 26488 KB Output is correct
18 Correct 43 ms 26360 KB Output is correct
19 Correct 2388 ms 371768 KB Output is correct
20 Correct 2319 ms 371816 KB Output is correct
21 Correct 2372 ms 371688 KB Output is correct
22 Correct 2105 ms 370944 KB Output is correct
23 Correct 1573 ms 371112 KB Output is correct
24 Correct 1390 ms 370280 KB Output is correct
25 Correct 2226 ms 371632 KB Output is correct
26 Correct 2169 ms 371684 KB Output is correct
27 Correct 2052 ms 371508 KB Output is correct
28 Correct 1399 ms 370896 KB Output is correct
29 Correct 1500 ms 370920 KB Output is correct
30 Correct 1268 ms 369940 KB Output is correct
31 Correct 2459 ms 372076 KB Output is correct
32 Correct 2511 ms 372340 KB Output is correct
33 Correct 2411 ms 371840 KB Output is correct
34 Correct 2245 ms 371432 KB Output is correct
35 Correct 1658 ms 371304 KB Output is correct
36 Correct 1435 ms 370392 KB Output is correct
37 Correct 2425 ms 372284 KB Output is correct
38 Correct 2433 ms 372360 KB Output is correct
39 Correct 2389 ms 372412 KB Output is correct
40 Correct 1411 ms 370792 KB Output is correct
41 Correct 1489 ms 370868 KB Output is correct
42 Correct 1267 ms 369752 KB Output is correct
43 Correct 2446 ms 374036 KB Output is correct
44 Correct 2459 ms 374376 KB Output is correct
45 Correct 2407 ms 374320 KB Output is correct
46 Correct 2150 ms 372532 KB Output is correct
47 Correct 1621 ms 372712 KB Output is correct
48 Correct 1431 ms 370172 KB Output is correct
49 Correct 2335 ms 374124 KB Output is correct
50 Correct 2376 ms 374248 KB Output is correct
51 Correct 2223 ms 373916 KB Output is correct
52 Correct 1401 ms 372548 KB Output is correct
53 Correct 1509 ms 371560 KB Output is correct