oj.uz

Submission #255379

# Submission time Handle Problem Language Result Execution time Memory
255379 2020-07-31T20:48:59 Z islingr Examination (JOI19_examination) C++14
20 / 100
 338 ms 12756 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define sz(x) int((x).size())
#define eb(x...) emplace_back(x)
#define lb(x...) lower_bound(x)
#define all(x) begin(x), end(x)

using ll = int64_t;

const int N = 1 << 17;

int n, m;
int t[4 * N];
int query(int l, int r) {
	int sum = 0;
	for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
		if (l & 1) sum += t[l++];
		if (r & 1) sum += t[--r];
	}
	return sum;
}
void update(int p, int x) {
	for (t[p += m] += x; p >>= 1; ) t[p] = t[p << 1] + t[p << 1|1];
}

struct point {
	int x, y, z, idx;
	bool operator<(const point &p) {
		return tuple<int, int, int, int>(-x, y, z, idx) < tuple<int, int, int, int>(-p.x, p.y, p.z, p.idx);
	}
} a[2 * N], tmp[2 * N];
vector<int> cmp;
int ans[N];

void cdq(int l, int r) {
	if (r - l == 1) return;
	int m = (l + r) / 2;
	cdq(l, m); cdq(m, r);
	vector<int> op;
	int i = l, j = m, k = l, cnt = 0;
	while (i < m && j < r) {
		if (a[j].y < a[i].y) {
			if (!a[i].idx) ++cnt, update(a[i].z, 1), op.eb(a[i].z);
			tmp[k] = a[i++];
		} else {
			if (a[j].idx) ans[a[j].idx] += cnt - query(0, a[j].z);
			tmp[k] = a[j++];
		}
		++k;
	}
	while (i < m) tmp[k++] = a[i++];
	while (j < r) {
		if (a[j].idx) ans[a[j].idx] += cnt - query(0, a[j].z);
		tmp[k++] = a[j++];
	}
	rep(i, l, r) a[i] = tmp[i];
	for (int p : op) update(p, -1);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int q; cin >> n >> q;
	rep(i, 0, n) {
		int x, y; cin >> x >> y;
		a[i] = {x, y, x + y, 0};
		cmp.eb(x + y);
	}
	rep(i, 0, q) {
		int x, y, z; cin >> x >> y >> z;
		a[i + n] = {--x, --y, --z, i + 1};
		cmp.eb(z);
	}
	sort(all(cmp)); cmp.resize(m = unique(all(cmp)) - begin(cmp));
	rep(i, 0, n + q) a[i].z = lb(all(cmp), a[i].z) - begin(cmp);
	sort(a, a + n + q); cdq(0, n + q);
	rep(i, 0, q) cout << ans[i + 1] << '\n';
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 8 ms 640 KB Output is correct
9 Correct 8 ms 640 KB Output is correct
10 Correct 7 ms 640 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Incorrect 5 ms 680 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 9456 KB Output is correct
2 Correct 225 ms 11928 KB Output is correct
3 Correct 228 ms 12016 KB Output is correct
4 Correct 201 ms 11120 KB Output is correct
5 Correct 143 ms 11100 KB Output is correct
6 Correct 97 ms 9964 KB Output is correct
7 Correct 219 ms 11628 KB Output is correct
8 Correct 213 ms 11884 KB Output is correct
9 Correct 203 ms 11652 KB Output is correct
10 Correct 122 ms 10864 KB Output is correct
11 Correct 185 ms 10856 KB Output is correct
12 Correct 75 ms 9588 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 9456 KB Output is correct
2 Correct 225 ms 11928 KB Output is correct
3 Correct 228 ms 12016 KB Output is correct
4 Correct 201 ms 11120 KB Output is correct
5 Correct 143 ms 11100 KB Output is correct
6 Correct 97 ms 9964 KB Output is correct
7 Correct 219 ms 11628 KB Output is correct
8 Correct 213 ms 11884 KB Output is correct
9 Correct 203 ms 11652 KB Output is correct
10 Correct 122 ms 10864 KB Output is correct
11 Correct 185 ms 10856 KB Output is correct
12 Correct 75 ms 9588 KB Output is correct
13 Incorrect 338 ms 12756 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 8 ms 640 KB Output is correct
9 Correct 8 ms 640 KB Output is correct
10 Correct 7 ms 640 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Incorrect 5 ms 680 KB Output isn't correct
13 Halted 0 ms 0 KB -