oj.uz

Submission #794491

# Submission time Handle Problem Language Result Execution time Memory
794491 2023-07-26T15:02:11 Z acatmeowmeow Examination (JOI19_examination) C++11
2 / 100
 2195 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;
int n, q, S[N +5], T[N + 5], X[N + 5], Y[N + 5], Z[N + 5], queryIndex[N + 5], arrIndex[N + 5], ans[N + 5];

struct subNode {
	int v = 0;
	subNode *lef = nullptr, *rig = nullptr;
	void extend() { if (!lef) lef = new subNode(), rig = new subNode(); }
	void update(int tl, int tr, int k) {
		if (tl == tr) v += 1;
		else {
			extend();
			int tm = (tl + tr)/2;
			if (k <= tm) lef->update(tl, tm, k);
			else rig->update(tm + 1, tr, k);
			v = lef->v + rig->v;
		}
	}
	int query(int tl, int tr, int l, int r) {
		if (l > r) return 0;
		else if (tl == l && tr == r) return v;
		else {
			extend();
			int tm = (tl + tr)/2;
			return lef->query(tl, tm, l, min(tm, r)) + rig->query(tm + 1, tr, max(l, tm + 1), r);
		}
	}
};

struct node {
	node *lef = nullptr, *rig = nullptr;
	subNode *root2 = new subNode();
	void extend() { if (!lef) lef = new node(), rig = new node(); }
	void update(int tl, int tr, int k, int k2) {
		if (tl == tr) root2->update(0, 1e9, k2);
		else {
			extend();
			int tm = (tl + tr)/2;
			if (k <= tm) lef->update(tl, tm, k, k2);
			else rig->update(tm + 1, tr, k, k2);
			root2->update(0, 1e9, k2);
		}
	}
	int query(int tl, int tr, int l, int r, int k2) {
		if (l > r) return 0;
		else if (tl == l && tr == r) return root2->query(0, 1e9, k2, 1e9);
		else {
			extend();
			int tm = (tl + tr)/2;
			return lef->query(tl, tm, l, min(tm, r), k2) + rig->query(tm + 1, tr, max(l, tm + 1), r, k2);
		}
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> S[i] >> T[i];
	for (int i = 1; i <= q; i++) cin >> X[i] >> Y[i] >> Z[i];

	iota(queryIndex + 1, queryIndex + q + 1, 1);
	sort(queryIndex + 1, queryIndex + q + 1, [&](int a, int b){
			if (Z[a] == Z[b]) return pair<int, int>(X[a], Y[a]) > pair<int, int>(X[b], Y[b]);
			else return Z[a] > Z[b];
	});

	iota(arrIndex + 1, arrIndex + n + 1, 1);
	sort(arrIndex + 1, arrIndex + n + 1, [&](int a, int b) {
			if (S[a] + T[a] == S[b] + T[b]) return pair<int, int>(S[a], T[a]) > pair<int, int>(S[b], T[b]);
			else return S[a] + T[a] > S[b] + T[b];
	});

	node *root = new node();

	for (int i = 1, arrPos = 1; i <= q; i++) {
		int pos = queryIndex[i];
		while (arrPos <= n && S[arrIndex[arrPos]] + T[arrIndex[arrPos]] >= Z[pos]) {
			root->update(0, 1e9, S[arrIndex[arrPos]], T[arrIndex[arrPos]]);	
			arrPos++;
		}
		ans[pos] = root->query(0, 1e9, X[pos], 1e9, Y[pos]);
	}

	for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
	return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 262 ms 247316 KB Output is correct
8 Correct 251 ms 247016 KB Output is correct
9 Correct 250 ms 247424 KB Output is correct
10 Correct 168 ms 168784 KB Output is correct
11 Correct 213 ms 195932 KB Output is correct
12 Correct 25 ms 652 KB Output is correct
13 Correct 260 ms 247068 KB Output is correct
14 Correct 251 ms 247184 KB Output is correct
15 Correct 246 ms 247228 KB Output is correct
16 Correct 160 ms 161828 KB Output is correct
17 Correct 150 ms 148060 KB Output is correct
18 Correct 18 ms 544 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2195 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 2195 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 262 ms 247316 KB Output is correct
8 Correct 251 ms 247016 KB Output is correct
9 Correct 250 ms 247424 KB Output is correct
10 Correct 168 ms 168784 KB Output is correct
11 Correct 213 ms 195932 KB Output is correct
12 Correct 25 ms 652 KB Output is correct
13 Correct 260 ms 247068 KB Output is correct
14 Correct 251 ms 247184 KB Output is correct
15 Correct 246 ms 247228 KB Output is correct
16 Correct 160 ms 161828 KB Output is correct
17 Correct 150 ms 148060 KB Output is correct
18 Correct 18 ms 544 KB Output is correct
19 Runtime error 2195 ms 1048576 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -