oj.uz

Submission #255382

# Submission time Handle Problem Language Result Execution time Memory
255382 2020-07-31T20:57:08 Z islingr Examination (JOI19_examination) C++14
20 / 100
 343 ms 9968 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 1 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 8 ms 640 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Incorrect 4 ms 640 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 221 ms 9452 KB Output is correct
2 Correct 223 ms 9584 KB Output is correct
3 Correct 218 ms 9584 KB Output is correct
4 Correct 196 ms 9584 KB Output is correct
5 Correct 140 ms 9456 KB Output is correct
6 Correct 95 ms 8940 KB Output is correct
7 Correct 212 ms 9324 KB Output is correct
8 Correct 224 ms 9580 KB Output is correct
9 Correct 213 ms 9324 KB Output is correct
10 Correct 124 ms 9196 KB Output is correct
11 Correct 207 ms 9324 KB Output is correct
12 Correct 73 ms 8684 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 9452 KB Output is correct
2 Correct 223 ms 9584 KB Output is correct
3 Correct 218 ms 9584 KB Output is correct
4 Correct 196 ms 9584 KB Output is correct
5 Correct 140 ms 9456 KB Output is correct
6 Correct 95 ms 8940 KB Output is correct
7 Correct 212 ms 9324 KB Output is correct
8 Correct 224 ms 9580 KB Output is correct
9 Correct 213 ms 9324 KB Output is correct
10 Correct 124 ms 9196 KB Output is correct
11 Correct 207 ms 9324 KB Output is correct
12 Correct 73 ms 8684 KB Output is correct
13 Incorrect 343 ms 9968 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 1 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 8 ms 640 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Incorrect 4 ms 640 KB Output isn't correct
13 Halted 0 ms 0 KB -