oj.uz

Submission #411962

# Submission time Handle Problem Language Result Execution time Memory
411962 2021-05-26T11:06:52 Z aryan12 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1976 ms 129896 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 5;
vector<pair<int, int> > a(N);
vector<int> operations(N);
map<int, int> cc, revcc;
vector<int> segMax(N * 12), segCnt(N * 12);

void UpdateMax(int l, int r, int pos, int qpos, int qval) {
	if(l == r) {
		segMax[pos] = max(segMax[pos], qval);
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= qpos) {
		UpdateMax(l, mid, pos * 2, qpos, qval);
	}
	else {
		UpdateMax(mid + 1, r, pos * 2 + 1, qpos, qval);
	}
	segMax[pos] = max(segMax[pos * 2], segMax[pos * 2 + 1]);
}

int QueryMax(int l, int r, int pos, int ql, int qr) {
	if(ql <= l && r <= qr)
		return segMax[pos];
	if(ql > r || l > qr)
		return 0LL;
	int mid = (l + r) >> 1;
	return max(QueryMax(l, mid, pos * 2, ql, qr), QueryMax(mid + 1, r, pos * 2 + 1, ql, qr));
}

void UpdateCnt(int l, int r, int pos, int qpos) {
	if(l == r) {
		segCnt[pos]++;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= qpos) {
		UpdateCnt(l, mid, pos * 2, qpos);
	}
	else {
		UpdateCnt(mid + 1, r, pos * 2 + 1, qpos);
	}
	segCnt[pos] = segCnt[pos * 2] + segCnt[pos * 2 + 1];
}

int QueryCnt(int l, int r, int pos, int ql, int qr) {
	if(ql <= l && r <= qr) {
		return segCnt[pos];
	}
	if(ql > r || l > qr)
		return 0LL;
	int mid = (l + r) >> 1;
	return QueryCnt(l, mid, pos * 2, ql, qr) + QueryCnt(mid + 1, r, pos * 2 + 1, ql, qr);
}

bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
	return a.second > b.second;
}

void Solve() {
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].first >> a[i].second;
		cc[a[i].first]++;
		cc[a[i].second]++;
	}
	for(int i = 1; i <= k; i++) {
		cin >> operations[i];
		cc[operations[i]]++;
	}
	int cnt = 1;
	for(auto i: cc) {
		cc[i.first] = cnt++;
		revcc[cnt - 1] = i.first;
		//cout << "Real value = " << i.first << ", coordinate compressed value = " << cnt - 1 << "\n";
		//cout << "revcc[" << cnt - 1 << "]->" << i.first << "\n";
	}
	for(int i = 1; i <= n; i++) {
		a[i].first = cc[a[i].first];
		a[i].second = cc[a[i].second];
	}
	for(int i = 1; i <= k; i++) {
		operations[i] = cc[operations[i]];
	}
	for(int i = 0; i < cnt * 4; i++) {
		segMax[i] = 0;
		segCnt[i] = 0;
	}
	for(int i = 1; i <= k; i++) {
		UpdateMax(1, cnt - 1, 1, operations[i], i);
		//UpdateCnt(1, cnt - 1, 1, operations[i]);
	}
	int ans = 0;
	operations[0] = 0;
	vector<pair<pair<int, int>, int> > temporary;
	for(int i = 1; i <= n; i++) {
		//cout << "i = " << i << ", a[i].first = " << a[i].first << ", a[i].second = " << a[i].second << "\n";
		if(a[i].first == a[i].second) {
			ans += revcc[a[i].first];
			continue;
		}
		int lastPosition = QueryMax(1, cnt - 1, 1, min(a[i].first, a[i].second), max(a[i].first, a[i].second) - 1);
		//cout << "Same as above -- lastPosition = " << lastPosition << "\n";
		temporary.push_back(make_pair(a[i], lastPosition));
	}
	sort(temporary.begin(), temporary.end(), cmp);
	int operationPos = k;
	for(int i = 0; i < temporary.size(); i++) {
		while(operationPos > temporary[i].second) {
			//cout << "operations[operationPos] = " << operations[operationPos] << "\n";
			UpdateCnt(1, cnt - 1, 1, operations[operationPos]);
			operationPos--;
		}
		//cout << "max of a[i] = " << max(temporary[i].first.first, temporary[i].first.second) << "\n";
		int numberofSwaps = QueryCnt(1, cnt - 1, 1, max(temporary[i].first.first, temporary[i].first.second), cnt - 1);
		//cout << "numberofSwaps = " << numberofSwaps << " lastPosition = " << temporary[i].second << ", a[i] = {" << temporary[i].first.first << ", " << temporary[i].first.second << "}" << "\n";
		if(temporary[i].second == 0) {
			if(numberofSwaps % 2 == 0) {
				ans += revcc[temporary[i].first.first];
			}
			else {
				ans += revcc[temporary[i].first.second];
			}
		}
		else {
			//cout << "a[i] = {" << temporary[i].first.first << ", " << temporary[i].first.second << "}\n";
			if(numberofSwaps % 2 == 0) {
				ans += revcc[max(temporary[i].first.second, temporary[i].first.first)];
			}
			else {
				ans += revcc[min(temporary[i].first.first, temporary[i].first.second)];
			}
		}
		//cout << "ans = " << ans << "\n";
	}
	cout << ans << "\n";
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'void Solve()':
fortune_telling2.cpp:115:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i = 0; i < temporary.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42700 KB Output is correct
2 Correct 20 ms 42828 KB Output is correct
3 Correct 25 ms 42956 KB Output is correct
4 Correct 21 ms 42948 KB Output is correct
5 Correct 21 ms 42960 KB Output is correct
6 Correct 21 ms 43036 KB Output is correct
7 Correct 21 ms 43004 KB Output is correct
8 Correct 21 ms 43024 KB Output is correct
9 Correct 21 ms 42940 KB Output is correct
10 Correct 23 ms 42740 KB Output is correct
11 Correct 24 ms 42880 KB Output is correct
12 Correct 21 ms 42912 KB Output is correct
13 Correct 24 ms 42948 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42700 KB Output is correct
2 Correct 20 ms 42828 KB Output is correct
3 Correct 25 ms 42956 KB Output is correct
4 Correct 21 ms 42948 KB Output is correct
5 Correct 21 ms 42960 KB Output is correct
6 Correct 21 ms 43036 KB Output is correct
7 Correct 21 ms 43004 KB Output is correct
8 Correct 21 ms 43024 KB Output is correct
9 Correct 21 ms 42940 KB Output is correct
10 Correct 23 ms 42740 KB Output is correct
11 Correct 24 ms 42880 KB Output is correct
12 Correct 21 ms 42912 KB Output is correct
13 Correct 24 ms 42948 KB Output is correct
14 Correct 59 ms 47036 KB Output is correct
15 Correct 115 ms 51572 KB Output is correct
16 Correct 175 ms 55616 KB Output is correct
17 Correct 231 ms 60400 KB Output is correct
18 Correct 253 ms 60384 KB Output is correct
19 Correct 227 ms 60428 KB Output is correct
20 Correct 248 ms 60428 KB Output is correct
21 Correct 266 ms 60456 KB Output is correct
22 Correct 155 ms 54972 KB Output is correct
23 Correct 128 ms 52412 KB Output is correct
24 Correct 127 ms 50480 KB Output is correct
25 Correct 177 ms 56380 KB Output is correct
26 Correct 184 ms 54404 KB Output is correct
27 Correct 183 ms 55500 KB Output is correct
28 Correct 159 ms 55400 KB Output is correct
29 Correct 187 ms 57924 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42700 KB Output is correct
2 Correct 20 ms 42828 KB Output is correct
3 Correct 25 ms 42956 KB Output is correct
4 Correct 21 ms 42948 KB Output is correct
5 Correct 21 ms 42960 KB Output is correct
6 Correct 21 ms 43036 KB Output is correct
7 Correct 21 ms 43004 KB Output is correct
8 Correct 21 ms 43024 KB Output is correct
9 Correct 21 ms 42940 KB Output is correct
10 Correct 23 ms 42740 KB Output is correct
11 Correct 24 ms 42880 KB Output is correct
12 Correct 21 ms 42912 KB Output is correct
13 Correct 24 ms 42948 KB Output is correct
14 Correct 59 ms 47036 KB Output is correct
15 Correct 115 ms 51572 KB Output is correct
16 Correct 175 ms 55616 KB Output is correct
17 Correct 231 ms 60400 KB Output is correct
18 Correct 253 ms 60384 KB Output is correct
19 Correct 227 ms 60428 KB Output is correct
20 Correct 248 ms 60428 KB Output is correct
21 Correct 266 ms 60456 KB Output is correct
22 Correct 155 ms 54972 KB Output is correct
23 Correct 128 ms 52412 KB Output is correct
24 Correct 127 ms 50480 KB Output is correct
25 Correct 177 ms 56380 KB Output is correct
26 Correct 184 ms 54404 KB Output is correct
27 Correct 183 ms 55500 KB Output is correct
28 Correct 159 ms 55400 KB Output is correct
29 Correct 187 ms 57924 KB Output is correct
30 Correct 461 ms 72716 KB Output is correct
31 Correct 768 ms 84816 KB Output is correct
32 Correct 1118 ms 99644 KB Output is correct
33 Correct 1836 ms 129708 KB Output is correct
34 Correct 388 ms 69556 KB Output is correct
35 Correct 1953 ms 129700 KB Output is correct
36 Correct 1976 ms 129804 KB Output is correct
37 Correct 1877 ms 129840 KB Output is correct
38 Correct 1851 ms 129780 KB Output is correct
39 Correct 1866 ms 129852 KB Output is correct
40 Correct 1726 ms 129404 KB Output is correct
41 Correct 1693 ms 129896 KB Output is correct
42 Correct 1808 ms 129780 KB Output is correct
43 Correct 1036 ms 129148 KB Output is correct
44 Correct 1067 ms 129112 KB Output is correct
45 Correct 1103 ms 128992 KB Output is correct
46 Correct 887 ms 90340 KB Output is correct
47 Correct 760 ms 77708 KB Output is correct
48 Correct 1196 ms 104828 KB Output is correct
49 Correct 1160 ms 104784 KB Output is correct