Submission #411962

#	Time	Username	Problem	Language	Result	Execution time	Memory
411962		aryan12	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1976 ms	129896 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65