oj.uz

Submission #656699

# Submission time Handle Problem Language Result Execution time Memory
656699 2022-11-08T04:53:59 Z TranGiaHuy1508 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1919 ms 173900 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);
	}

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

	map<int, int> compress;
	for (auto i: cards){
		compress[i.first] = compress[i.second] = 1;
	}
	for (auto i: qs) compress[i] = 1;

	int cp = 1;
	for (auto &[key, value]: compress) value = cp++;
	for (auto &i: cards) i = {compress[i.first], compress[i.second]};
	for (auto &i: MN) i = compress[i];
	for (auto &i: MX) i = compress[i];
	for (auto &i: qs) i = compress[i];

	map<int, int> revmap;
	for (auto [key, value]: compress) revmap[value] = key; 

	MaxImplicitSegtree ist(1, cp);
	
	for (int i = 0; i < q; 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";

	SumImplicitSegtree sst(1, cp);

	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], cp);
		}
	}

	// 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 << revmap[crr] << "\n";
		res += revmap[crr];
	}

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 1108 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 4 ms 1128 KB Output is correct
7 Correct 3 ms 1156 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 852 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 1108 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 4 ms 1128 KB Output is correct
7 Correct 3 ms 1156 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 40 ms 8872 KB Output is correct
15 Correct 91 ms 17372 KB Output is correct
16 Correct 142 ms 25860 KB Output is correct
17 Correct 196 ms 34528 KB Output is correct
18 Correct 192 ms 34284 KB Output is correct
19 Correct 201 ms 34424 KB Output is correct
20 Correct 201 ms 34944 KB Output is correct
21 Correct 179 ms 31768 KB Output is correct
22 Correct 111 ms 23720 KB Output is correct
23 Correct 95 ms 18836 KB Output is correct
24 Correct 84 ms 15172 KB Output is correct
25 Correct 115 ms 25816 KB Output is correct
26 Correct 117 ms 22952 KB Output is correct
27 Correct 138 ms 25256 KB Output is correct
28 Correct 124 ms 25036 KB Output is correct
29 Correct 165 ms 30628 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 1108 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 4 ms 1128 KB Output is correct
7 Correct 3 ms 1156 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 2 ms 852 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Correct 40 ms 8872 KB Output is correct
15 Correct 91 ms 17372 KB Output is correct
16 Correct 142 ms 25860 KB Output is correct
17 Correct 196 ms 34528 KB Output is correct
18 Correct 192 ms 34284 KB Output is correct
19 Correct 201 ms 34424 KB Output is correct
20 Correct 201 ms 34944 KB Output is correct
21 Correct 179 ms 31768 KB Output is correct
22 Correct 111 ms 23720 KB Output is correct
23 Correct 95 ms 18836 KB Output is correct
24 Correct 84 ms 15172 KB Output is correct
25 Correct 115 ms 25816 KB Output is correct
26 Correct 117 ms 22952 KB Output is correct
27 Correct 138 ms 25256 KB Output is correct
28 Correct 124 ms 25036 KB Output is correct
29 Correct 165 ms 30628 KB Output is correct
30 Correct 505 ms 68020 KB Output is correct
31 Correct 716 ms 90608 KB Output is correct
32 Correct 1069 ms 117948 KB Output is correct
33 Correct 1893 ms 170788 KB Output is correct
34 Correct 420 ms 62140 KB Output is correct
35 Correct 1919 ms 172720 KB Output is correct
36 Correct 1869 ms 170340 KB Output is correct
37 Correct 1896 ms 172572 KB Output is correct
38 Correct 1858 ms 171532 KB Output is correct
39 Correct 1860 ms 173884 KB Output is correct
40 Correct 1587 ms 151720 KB Output is correct
41 Correct 1839 ms 173860 KB Output is correct
42 Correct 1831 ms 173900 KB Output is correct
43 Correct 855 ms 142916 KB Output is correct
44 Correct 867 ms 143004 KB Output is correct
45 Correct 833 ms 143040 KB Output is correct
46 Correct 728 ms 93104 KB Output is correct
47 Correct 633 ms 67848 KB Output is correct
48 Correct 1091 ms 124176 KB Output is correct
49 Correct 1057 ms 123944 KB Output is correct