Submission #377507

#	Time	Username	Problem	Language	Result	Execution time	Memory
377507		reymontada61	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	1125 ms	7892 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, k, ans;
vector<pair<pair<int, int>, int>> crs; 
vector<pair<int, int>> qs;

const int MXN = 40005;

int seg[MXN * 4];

void build(int ind, int l, int r) {
	if (l == r) {
		seg[ind] = qs[l].second;
		return;
	}
	int m = (l + r) / 2;
	build(ind*2, l, m);
	build(ind*2+1, m+1, r);
	seg[ind] = max(seg[ind*2], seg[ind*2+1]);
}

int query(int ind, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return seg[ind];
	if (ql > r || qr < l) return -1;
	int m = (l + r) / 2;
	return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr));
}

signed main() {
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> n >> k;
	for (int i=0; i<n; i++) {
		int a, b;
		cin >> a >> b;
		
		if (a == b) {
			ans += a;
			continue;
		}
		
		int s = 0;
		if (a > b) {
			swap(a, b); s = 1;
		}
		
		crs.push_back({{a, b}, s});
		
	}
	
	n = crs.size();
	
	for (int i=0; i<k; i++) {
		int x;
		cin >> x;
		qs.push_back({x, i});
	}
	
	sort(qs.begin(), qs.end());
	
	build(1, 0, k-1);
	
	for (auto x: crs) {
		int a = x.first.first, b = x.first.second;
		
		int e = lower_bound(qs.begin(), qs.end(), make_pair(a, 0ll)) - qs.begin();
		int f = upper_bound(qs.begin(), qs.end(), make_pair(b-1, k)) - qs.begin() - 1;
		
		int ls = query(1, 0, k-1, e, f);
		
		int up = x.second;
		if (ls != -1) up = 1;
		
		int flips = 0;
		
		for (int j=f+1; j<qs.size(); j++) {
			if (qs[j].second > ls) flips++;
		}
		
		if (flips % 2 == 1) up = 1 - up;
		
		if (up) ans += b;
		else ans += a;
		
	}
	
	cout << ans << endl;

}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:79:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for (int j=f+1; j<qs.size(); j++) {
      |                   ~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 0 / 65