oj.uz

Submission #470451

# Submission time Handle Problem Language Result Execution time Memory
470451 2021-09-03T19:57:58 Z Namnamseo Examination (JOI19_examination) C++17
100 / 100
 1502 ms 286172 KB 
#include <algorithm>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using pp=pair<int,int>;
using vi=vector<int>;
const int maxn = int(1e5) + 10;
#define all(v) v.begin(), v.end()
#define pb push_back
#define x first
#define y second

int n;
pp d[maxn];

struct MergeSortTree {
	int m; vi xs, *t;

	void init(int l, int r) {
		xs.resize(r-l);
		for (m=1; m<r-l; m*=2);
		t = new vector<int>[m*2];
		for (int i=l; i<r; ++i) xs[i-l] = d[i].x;
		sort(all(xs));
		for (int i=l; i<r; ++i) {
			int x, y; tie(x, y) = d[i];
			x = lower_bound(all(xs), x) - xs.begin();
			t[x+m].pb(y);
		}
		for (int i=0; i<int(xs.size()); ++i) sort(all(t[m+i]));
		for (int i=m-1; 1<=i; --i) {
			auto &v=t[i], &vl=t[i*2], &vr=t[i*2+1];
			v.resize(vl.size()+vr.size());
			merge(all(vl), all(vr), v.begin());
		}
	}

	int rect(int l, int r, int d, int u) {
		l = lower_bound(all(xs), l) - xs.begin();
		r = upper_bound(all(xs), r) - xs.begin() - 1;
		if (l > r || d > u) return 0;
		int ret = 0;
		auto f = [&](vi &v) { ret += upper_bound(all(v), u) - lower_bound(all(v), d); };
		for (l+=m, r+=m; l<=r; l/=2, r/=2) {
			if (l%2 == 1) f(t[l++]);
			if (r%2 == 0) f(t[r--]);
		}
		return ret;
	}
} mst[262144];

void init(int p, int l, int r) {
	mst[p].init(l, r);
	if (l+1 == r) return;
	int md = (l+r)/2;
	init(p*2, l, md); init(p*2+1, md, r);
}

struct { int l, r, d, u; } Q;
int rect(int sl, int sr, int p, int l, int r) {
	if (sr<=l || r<=sl) return 0;
	if (sl<=l && r<=sr) return mst[p].rect(Q.l, Q.r, Q.d, Q.u);
	int md = (l+r)/2;
	return rect(sl, sr, p*2, l, md) + rect(sl, sr, p*2+1, md, r);
}

bool pcomp(const pp &a, const pp &b) {
	return (a.x+a.y) < (b.x+b.y);
}

int main() { cin.tie(0)->sync_with_stdio(0);
	int q; cin >> n >> q;
	for (int i=0; i<n; ++i) cin >> d[i].x >> d[i].y;
	sort(d, d+n, pcomp);
	init(1, 0, n);

	for(;q--;) {
		int x, y, s; cin >> x >> y >> s;
		int j = lower_bound(d, d+n, pp{s, 0}, pcomp)-d;
		const int inf = int(1e9) + 10;
		Q = {x, inf, y, inf};
		cout << rect(j, n, 1, 0, n) << '\n';
	}
	return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10572 KB Output is correct
2 Correct 6 ms 10584 KB Output is correct
3 Correct 6 ms 10572 KB Output is correct
4 Correct 7 ms 10572 KB Output is correct
5 Correct 6 ms 10572 KB Output is correct
6 Correct 6 ms 10572 KB Output is correct
7 Correct 24 ms 16272 KB Output is correct
8 Correct 23 ms 16284 KB Output is correct
9 Correct 23 ms 16232 KB Output is correct
10 Correct 20 ms 16204 KB Output is correct
11 Correct 21 ms 15240 KB Output is correct
12 Correct 18 ms 15072 KB Output is correct
13 Correct 20 ms 16160 KB Output is correct
14 Correct 23 ms 16204 KB Output is correct
15 Correct 21 ms 16204 KB Output is correct
16 Correct 17 ms 14796 KB Output is correct
17 Correct 19 ms 16244 KB Output is correct
18 Correct 12 ms 14668 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 280216 KB Output is correct
2 Correct 838 ms 280284 KB Output is correct
3 Correct 826 ms 280316 KB Output is correct
4 Correct 735 ms 264244 KB Output is correct
5 Correct 528 ms 227260 KB Output is correct
6 Correct 446 ms 222532 KB Output is correct
7 Correct 824 ms 280228 KB Output is correct
8 Correct 809 ms 280308 KB Output is correct
9 Correct 790 ms 280312 KB Output is correct
10 Correct 325 ms 211008 KB Output is correct
11 Correct 610 ms 261660 KB Output is correct
12 Correct 294 ms 210116 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 280216 KB Output is correct
2 Correct 838 ms 280284 KB Output is correct
3 Correct 826 ms 280316 KB Output is correct
4 Correct 735 ms 264244 KB Output is correct
5 Correct 528 ms 227260 KB Output is correct
6 Correct 446 ms 222532 KB Output is correct
7 Correct 824 ms 280228 KB Output is correct
8 Correct 809 ms 280308 KB Output is correct
9 Correct 790 ms 280312 KB Output is correct
10 Correct 325 ms 211008 KB Output is correct
11 Correct 610 ms 261660 KB Output is correct
12 Correct 294 ms 210116 KB Output is correct
13 Correct 1424 ms 280732 KB Output is correct
14 Correct 1497 ms 280768 KB Output is correct
15 Correct 881 ms 280256 KB Output is correct
16 Correct 1045 ms 264656 KB Output is correct
17 Correct 1063 ms 227692 KB Output is correct
18 Correct 656 ms 222744 KB Output is correct
19 Correct 1400 ms 280800 KB Output is correct
20 Correct 1495 ms 280772 KB Output is correct
21 Correct 1392 ms 280736 KB Output is correct
22 Correct 326 ms 211056 KB Output is correct
23 Correct 596 ms 261472 KB Output is correct
24 Correct 290 ms 210052 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10572 KB Output is correct
2 Correct 6 ms 10584 KB Output is correct
3 Correct 6 ms 10572 KB Output is correct
4 Correct 7 ms 10572 KB Output is correct
5 Correct 6 ms 10572 KB Output is correct
6 Correct 6 ms 10572 KB Output is correct
7 Correct 24 ms 16272 KB Output is correct
8 Correct 23 ms 16284 KB Output is correct
9 Correct 23 ms 16232 KB Output is correct
10 Correct 20 ms 16204 KB Output is correct
11 Correct 21 ms 15240 KB Output is correct
12 Correct 18 ms 15072 KB Output is correct
13 Correct 20 ms 16160 KB Output is correct
14 Correct 23 ms 16204 KB Output is correct
15 Correct 21 ms 16204 KB Output is correct
16 Correct 17 ms 14796 KB Output is correct
17 Correct 19 ms 16244 KB Output is correct
18 Correct 12 ms 14668 KB Output is correct
19 Correct 843 ms 280216 KB Output is correct
20 Correct 838 ms 280284 KB Output is correct
21 Correct 826 ms 280316 KB Output is correct
22 Correct 735 ms 264244 KB Output is correct
23 Correct 528 ms 227260 KB Output is correct
24 Correct 446 ms 222532 KB Output is correct
25 Correct 824 ms 280228 KB Output is correct
26 Correct 809 ms 280308 KB Output is correct
27 Correct 790 ms 280312 KB Output is correct
28 Correct 325 ms 211008 KB Output is correct
29 Correct 610 ms 261660 KB Output is correct
30 Correct 294 ms 210116 KB Output is correct
31 Correct 1424 ms 280732 KB Output is correct
32 Correct 1497 ms 280768 KB Output is correct
33 Correct 881 ms 280256 KB Output is correct
34 Correct 1045 ms 264656 KB Output is correct
35 Correct 1063 ms 227692 KB Output is correct
36 Correct 656 ms 222744 KB Output is correct
37 Correct 1400 ms 280800 KB Output is correct
38 Correct 1495 ms 280772 KB Output is correct
39 Correct 1392 ms 280736 KB Output is correct
40 Correct 326 ms 211056 KB Output is correct
41 Correct 596 ms 261472 KB Output is correct
42 Correct 290 ms 210052 KB Output is correct
43 Correct 1425 ms 286160 KB Output is correct
44 Correct 1413 ms 286172 KB Output is correct
45 Correct 1446 ms 286024 KB Output is correct
46 Correct 1012 ms 284608 KB Output is correct
47 Correct 1066 ms 228868 KB Output is correct
48 Correct 512 ms 222368 KB Output is correct
49 Correct 1502 ms 286032 KB Output is correct
50 Correct 1364 ms 285980 KB Output is correct
51 Correct 1429 ms 286092 KB Output is correct
52 Correct 527 ms 212588 KB Output is correct
53 Correct 585 ms 283728 KB Output is correct