oj.uz

Submission #845990

# Submission time Handle Problem Language Result Execution time Memory
845990 2023-09-07T02:43:32 Z LeonaRaging Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 1625 ms 175096 KB 
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define SZ(val) (int)val.size()
#define all(val) val.begin(), val.end()

const int maxn = 5e5 + 4;

int n, k, a[maxn], b[maxn], q[maxn], idx[maxn], node[maxn], L[maxn], R[maxn], bst[maxn];
vector<int> vals, que[maxn];

struct seg_tree {
	vector<int> t;
	seg_tree() {
		t.resize(4 * maxn);
	}
	void init() {
		t.clear(); t.resize(4 * maxn);
	}
	void update(int pos, int val, int v = 1, int l = 1, int r = maxn - 1) {
		if (l == r) {
			t[v] += val;
			return;
		}
		int m = (l + r) / 2;
		if (pos <= m) update(pos, val, 2 * v, l, m);
		else update(pos, val, 2 * v + 1, m + 1, r);
		t[v] = t[2 * v] + t[2 * v + 1];
	}
	int get(int l, int r, int v = 1, int tl = 1, int tr = maxn - 1) {
		if (tl > r || tr < l) return 0;
		if (tl >= l && tr <= r) return t[v];
		int m = (tl + tr) / 2;
		return get(l, r, 2 * v, tl, m) + get(l, r, 2 * v + 1, m + 1, tr);
	}
} IT1;

struct persistent {
	vector<int> t, L, R;
	int num;
	persistent() {
		num = 0;
		t.resize(1e7);
		L.resize(1e7);
		R.resize(1e7);
	}
	int update(int pos, int val, int v, int l = 1, int r = maxn - 1) {
		if (pos < l || pos > r) return v;
		if (l == r) {
			t[++num] = t[v] + val;
			return num;
		}
		int m = (l + r) / 2, cur = ++num;
		L[cur] = update(pos, val, L[v], l, m);
		R[cur] = update(pos, val, R[v], m + 1, r);
		t[cur] = t[L[cur]] + t[R[cur]];
		return cur;
	}
	int get(int l, int r, int v, int tl = 1, int tr = maxn - 1) {
		if (tl > r || tr < l) return 0;
		if (tl >= l && tr <= r) return t[v];
		int m = (tl + tr) / 2;
		return get(l, r, L[v], tl, m) + get(l, r, R[v], m + 1, tr);
	}
} IT2;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i], idx[i] = i;
		vals.pb(a[i]); vals.pb(b[i]);
	}
	for (int i = 1; i <= k; i++) {
		cin >> q[i];
		vals.pb(q[i]);
	}
	sort(all(vals));
	vals.erase(unique(all(vals)), vals.end());
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(all(vals), a[i]) - vals.begin() + 1;
		b[i] = lower_bound(all(vals), b[i]) - vals.begin() + 1;
	}
	for (int i = k; i >= 1; i--) {
		q[i] = lower_bound(all(vals), q[i]) - vals.begin() + 1;
		node[i] = IT2.update(q[i], 1, node[i + 1]);
	}
	// for (int i = 1; i <= n; i++)
		// clog << a[i] << ' ' << b[i] << endl;
	// for (int i = 1; i <= k; i++)
		// clog << q[i] << endl;
	for (int i = 1; i <= n; i++)
		L[i] = 1, R[i] = k;
	for (int t = 0; t < 18; t++) {
		for (int i = 1; i <= n; i++)
			que[(L[i] + R[i]) / 2].pb(i);
		IT1.init();
		for (int i = k; i >= 1; i--) {
			IT1.update(q[i], 1);
			// if (i == 3) clog << q[i] << ' ' << IT1.get(1, 1);
			for (int j : que[i])
				if (IT1.get(min(a[j], b[j]), max(a[j], b[j]) - 1)) {
					bst[j] = i;
					L[j] = i + 1;
				}
				else R[j] = i - 1;
			que[i].clear();
		}
	}
	long long res = 0;
	for (int i = 1; i <= n; i++) {
		int p = bst[i], lo = min(a[i], b[i]), hi = max(a[i], b[i]);
		int cnt = IT2.get(hi, SZ(vals), node[p + 1]);
		if (!p) res += (cnt & 1 ? vals[b[i] - 1] : vals[a[i] - 1]);
		else res += (cnt & 1 ? vals[lo - 1] : vals[hi - 1]);
	}
	cout << res;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 150360 KB Output is correct
2 Correct 28 ms 150356 KB Output is correct
3 Correct 29 ms 150536 KB Output is correct
4 Correct 31 ms 150616 KB Output is correct
5 Correct 30 ms 150508 KB Output is correct
6 Correct 30 ms 150620 KB Output is correct
7 Correct 29 ms 150648 KB Output is correct
8 Correct 30 ms 150620 KB Output is correct
9 Correct 29 ms 150456 KB Output is correct
10 Correct 28 ms 150364 KB Output is correct
11 Correct 28 ms 150364 KB Output is correct
12 Correct 29 ms 150364 KB Output is correct
13 Correct 28 ms 150548 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 150360 KB Output is correct
2 Correct 28 ms 150356 KB Output is correct
3 Correct 29 ms 150536 KB Output is correct
4 Correct 31 ms 150616 KB Output is correct
5 Correct 30 ms 150508 KB Output is correct
6 Correct 30 ms 150620 KB Output is correct
7 Correct 29 ms 150648 KB Output is correct
8 Correct 30 ms 150620 KB Output is correct
9 Correct 29 ms 150456 KB Output is correct
10 Correct 28 ms 150364 KB Output is correct
11 Correct 28 ms 150364 KB Output is correct
12 Correct 29 ms 150364 KB Output is correct
13 Correct 28 ms 150548 KB Output is correct
14 Correct 98 ms 151632 KB Output is correct
15 Correct 177 ms 152628 KB Output is correct
16 Correct 266 ms 153808 KB Output is correct
17 Correct 352 ms 154832 KB Output is correct
18 Correct 349 ms 154968 KB Output is correct
19 Correct 356 ms 154964 KB Output is correct
20 Correct 332 ms 154972 KB Output is correct
21 Correct 380 ms 155128 KB Output is correct
22 Correct 261 ms 154536 KB Output is correct
23 Correct 259 ms 154324 KB Output is correct
24 Correct 249 ms 154324 KB Output is correct
25 Correct 267 ms 154576 KB Output is correct
26 Correct 260 ms 154500 KB Output is correct
27 Correct 265 ms 155164 KB Output is correct
28 Correct 267 ms 155088 KB Output is correct
29 Correct 263 ms 155776 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 150360 KB Output is correct
2 Correct 28 ms 150356 KB Output is correct
3 Correct 29 ms 150536 KB Output is correct
4 Correct 31 ms 150616 KB Output is correct
5 Correct 30 ms 150508 KB Output is correct
6 Correct 30 ms 150620 KB Output is correct
7 Correct 29 ms 150648 KB Output is correct
8 Correct 30 ms 150620 KB Output is correct
9 Correct 29 ms 150456 KB Output is correct
10 Correct 28 ms 150364 KB Output is correct
11 Correct 28 ms 150364 KB Output is correct
12 Correct 29 ms 150364 KB Output is correct
13 Correct 28 ms 150548 KB Output is correct
14 Correct 98 ms 151632 KB Output is correct
15 Correct 177 ms 152628 KB Output is correct
16 Correct 266 ms 153808 KB Output is correct
17 Correct 352 ms 154832 KB Output is correct
18 Correct 349 ms 154968 KB Output is correct
19 Correct 356 ms 154964 KB Output is correct
20 Correct 332 ms 154972 KB Output is correct
21 Correct 380 ms 155128 KB Output is correct
22 Correct 261 ms 154536 KB Output is correct
23 Correct 259 ms 154324 KB Output is correct
24 Correct 249 ms 154324 KB Output is correct
25 Correct 267 ms 154576 KB Output is correct
26 Correct 260 ms 154500 KB Output is correct
27 Correct 265 ms 155164 KB Output is correct
28 Correct 267 ms 155088 KB Output is correct
29 Correct 263 ms 155776 KB Output is correct
30 Correct 646 ms 155088 KB Output is correct
31 Correct 913 ms 158892 KB Output is correct
32 Correct 1211 ms 164320 KB Output is correct
33 Incorrect 1625 ms 175096 KB Output isn't correct
34 Halted 0 ms 0 KB -