oj.uz

Submission #656692

# Submission time Handle Problem Language Result Execution time Memory
656692 2022-11-08T03:57:02 Z TranGiaHuy1508 Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 407 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

#define int long long

struct MaxImplicitSegtree{
	int lb, rb;
	MaxImplicitSegtree *leftnode, *rightnode;
	int mx;

	MaxImplicitSegtree(int L, int R): lb(L), rb(R), leftnode(nullptr), rightnode(nullptr), mx(-1) {}

	void extend(){
		if (lb == rb) return;
		if (leftnode) return;
		int mid = (lb + rb) >> 1;
		leftnode = new MaxImplicitSegtree(lb, mid);
		rightnode = new MaxImplicitSegtree(mid+1, rb);
	}

	int get(int l, int r){
		if (l <= lb && rb <= r) return mx;
		if (lb > r || rb < l) return -1;

		extend();
		return max(leftnode->get(l, r), rightnode->get(l, r));
	}

	void update(int x, int val){
		if (lb == x && rb == x) mx = val;
		else{
			extend();
			int mid = (lb + rb) >> 1;
			if (x <= mid) leftnode->update(x, val);
			else rightnode->update(x, val);

			mx = max(leftnode->mx, rightnode->mx);
		}
	}
};

struct SumImplicitSegtree{
	int lb, rb;
	SumImplicitSegtree *leftnode, *rightnode;
	int sum;

	SumImplicitSegtree(int L, int R): lb(L), rb(R), leftnode(nullptr), rightnode(nullptr), sum(0) {}

	void extend(){
		if (lb == rb) return;
		if (leftnode) return;
		int mid = (lb + rb) >> 1;
		leftnode = new SumImplicitSegtree(lb, mid);
		rightnode = new SumImplicitSegtree(mid+1, rb);
	}

	int get(int l, int r){
		if (l <= lb && rb <= r) return sum;
		if (lb > r || rb < l) return 0;

		extend();
		return leftnode->get(l, r) + rightnode->get(l, r);
	}

	void update(int x, int delta){
		if (lb == x && rb == x) sum += delta;
		else{
			extend();
			int mid = (lb + rb) >> 1;
			if (x <= mid) leftnode->update(x, delta);
			else rightnode->update(x, delta);

			sum = leftnode->sum + rightnode->sum;
		}
	}
};

const int inf = 1e9 + 1;
int n, q;
vector<pair<int, int>> cards;
vector<int> MN, MX, qs, lst, inv;

void main_program(){
	cin >> n >> q;
	qs.resize(q);
	cards.resize(n);
	MN.resize(n);
	MX.resize(n);
	lst.assign(n, -1);
	inv.assign(n, 0);

	for (int i = 0; i < n; i++){
		int A, B; cin >> A >> B;
		cards[i] = {A, B};
		MN[i] = min(A, B); MX[i] = max(A, B);
	}

	MaxImplicitSegtree ist(1, inf);
	SumImplicitSegtree sst(1, inf);

	for (int i = 0; i < q; i++){
		cin >> qs[i];
		ist.update(qs[i], i);
	}

	for (int i = 0; i < n; i++){
		if (MX[i] > MN[i]) lst[i] = ist.get(MN[i], MX[i] - 1);
	}

	// for (int i = 0; i < n; i++) cout << lst[i] << " ";
	// cout << "\n";

	vector<vector<int>> radix(q + 1);
	for (int i = 0; i < n; i++)	radix[lst[i] + 1].push_back(i);

	for (int i = q-1; i >= 0; i--){
		sst.update(qs[i], 1);
		for (auto j: radix[i]){
			// cout << j << "\n";
			inv[j] = sst.get(MX[j], inf);
		}
	}

	// for (int i = 0; i < n; i++) cout << inv[i] << " ";
	// cout << "\n";

	long long res = 0;
	for (int i = 0; i < n; i++){
		int crr;
		if (lst[i] >= 0) crr = MX[i];
		else crr = cards[i].first;

		if (inv[i] & 1) crr = cards[i].first + cards[i].second - crr;

		// cout << crr << "\n";
		res += crr;
	}

	cout << res << "\n";
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4436 KB Output is correct
2 Correct 6 ms 6100 KB Output is correct
3 Correct 10 ms 8428 KB Output is correct
4 Correct 9 ms 8464 KB Output is correct
5 Correct 10 ms 8592 KB Output is correct
6 Correct 9 ms 8276 KB Output is correct
7 Correct 9 ms 8788 KB Output is correct
8 Correct 7 ms 7124 KB Output is correct
9 Correct 5 ms 4324 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 7 ms 7252 KB Output is correct
12 Correct 8 ms 7124 KB Output is correct
13 Correct 9 ms 7380 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4436 KB Output is correct
2 Correct 6 ms 6100 KB Output is correct
3 Correct 10 ms 8428 KB Output is correct
4 Correct 9 ms 8464 KB Output is correct
5 Correct 10 ms 8592 KB Output is correct
6 Correct 9 ms 8276 KB Output is correct
7 Correct 9 ms 8788 KB Output is correct
8 Correct 7 ms 7124 KB Output is correct
9 Correct 5 ms 4324 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 7 ms 7252 KB Output is correct
12 Correct 8 ms 7124 KB Output is correct
13 Correct 9 ms 7380 KB Output is correct
14 Correct 79 ms 66208 KB Output is correct
15 Correct 163 ms 121360 KB Output is correct
16 Correct 235 ms 173300 KB Output is correct
17 Correct 307 ms 229948 KB Output is correct
18 Correct 324 ms 222980 KB Output is correct
19 Correct 295 ms 225852 KB Output is correct
20 Correct 317 ms 241592 KB Output is correct
21 Correct 263 ms 199224 KB Output is correct
22 Correct 80 ms 17364 KB Output is correct
23 Correct 55 ms 14424 KB Output is correct
24 Correct 60 ms 12188 KB Output is correct
25 Correct 81 ms 21372 KB Output is correct
26 Correct 240 ms 184136 KB Output is correct
27 Correct 259 ms 199904 KB Output is correct
28 Correct 261 ms 191552 KB Output is correct
29 Correct 307 ms 222232 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4436 KB Output is correct
2 Correct 6 ms 6100 KB Output is correct
3 Correct 10 ms 8428 KB Output is correct
4 Correct 9 ms 8464 KB Output is correct
5 Correct 10 ms 8592 KB Output is correct
6 Correct 9 ms 8276 KB Output is correct
7 Correct 9 ms 8788 KB Output is correct
8 Correct 7 ms 7124 KB Output is correct
9 Correct 5 ms 4324 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 7 ms 7252 KB Output is correct
12 Correct 8 ms 7124 KB Output is correct
13 Correct 9 ms 7380 KB Output is correct
14 Correct 79 ms 66208 KB Output is correct
15 Correct 163 ms 121360 KB Output is correct
16 Correct 235 ms 173300 KB Output is correct
17 Correct 307 ms 229948 KB Output is correct
18 Correct 324 ms 222980 KB Output is correct
19 Correct 295 ms 225852 KB Output is correct
20 Correct 317 ms 241592 KB Output is correct
21 Correct 263 ms 199224 KB Output is correct
22 Correct 80 ms 17364 KB Output is correct
23 Correct 55 ms 14424 KB Output is correct
24 Correct 60 ms 12188 KB Output is correct
25 Correct 81 ms 21372 KB Output is correct
26 Correct 240 ms 184136 KB Output is correct
27 Correct 259 ms 199904 KB Output is correct
28 Correct 261 ms 191552 KB Output is correct
29 Correct 307 ms 222232 KB Output is correct
30 Runtime error 407 ms 262144 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -