oj.uz

Submission #794520

# Submission time Handle Problem Language Result Execution time Memory
794520 2023-07-26T15:17:44 Z acatmeowmeow Examination (JOI19_examination) C++11
2 / 100
 1805 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, 2*N, 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, 2*N, 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, 2*N, k2, 2*N);
		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];
	
	vector<int> mp1, mp2;
	for (int i = 1; i <= n; i++) mp1.push_back(S[i]), mp2.push_back(T[i]);
	for (int i = 1; i <= q; i++) mp1.push_back(X[i]), mp2.push_back(Y[i]);
	sort(mp1.begin(), mp1.end());
	sort(mp2.begin(), mp2.end());
	mp1.erase(unique(mp1.begin(), mp1.end()), mp1.end());
	mp2.erase(unique(mp2.begin(), mp2.end()), mp2.end());
	auto find = [&](int v, vector<int>&mp) { return lower_bound(mp.begin(), mp.end(), v) - mp.begin(); };

	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]) {
			int mpS = find(S[arrIndex[arrPos]], mp1), mpT = find(T[arrIndex[arrPos]], mp2);
			root->update(0, 2*N, mpS, mpT);	
			arrPos++;
		}
		int mpX = find(X[pos], mp1), mpY = find(Y[pos], mp2);
		ans[pos] = root->query(0, 2*N, mpX, 2*N, mpY);
	}

	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 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 51 ms 33744 KB Output is correct
8 Correct 56 ms 33836 KB Output is correct
9 Correct 52 ms 33692 KB Output is correct
10 Correct 22 ms 13604 KB Output is correct
11 Correct 24 ms 12404 KB Output is correct
12 Correct 9 ms 596 KB Output is correct
13 Correct 63 ms 33744 KB Output is correct
14 Correct 48 ms 33584 KB Output is correct
15 Correct 47 ms 33612 KB Output is correct
16 Correct 17 ms 10280 KB Output is correct
17 Correct 27 ms 12172 KB Output is correct
18 Correct 7 ms 596 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1805 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 1805 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 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 51 ms 33744 KB Output is correct
8 Correct 56 ms 33836 KB Output is correct
9 Correct 52 ms 33692 KB Output is correct
10 Correct 22 ms 13604 KB Output is correct
11 Correct 24 ms 12404 KB Output is correct
12 Correct 9 ms 596 KB Output is correct
13 Correct 63 ms 33744 KB Output is correct
14 Correct 48 ms 33584 KB Output is correct
15 Correct 47 ms 33612 KB Output is correct
16 Correct 17 ms 10280 KB Output is correct
17 Correct 27 ms 12172 KB Output is correct
18 Correct 7 ms 596 KB Output is correct
19 Runtime error 1805 ms 1048576 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -