oj.uz

Submission #255375

# Submission time Handle Problem Language Result Execution time Memory
255375 2020-07-31T20:42:04 Z islingr Examination (JOI19_examination) C++14
0 / 100
 225 ms 9456 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;
	int 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 + 1);
			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 + 1);
		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 1 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 1 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 11 ms 640 KB Output is correct
10 Correct 8 ms 640 KB Output is correct
11 Incorrect 6 ms 640 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 9456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 9456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 11 ms 640 KB Output is correct
10 Correct 8 ms 640 KB Output is correct
11 Incorrect 6 ms 640 KB Output isn't correct
12 Halted 0 ms 0 KB -