Submission #519296

#	Time	Username	Problem	Language	Result	Execution time	Memory
519296		amunduzbaev	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	173 ms	10436 KiB

fortune_telling2

#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 2e5 + 5;
int a[N], b[N], f[N], t[N];
struct ST{
	int tree[N<<2], sum[N<<2];
	
	void init(){
		memset(tree, 127, sizeof tree);
	}
	
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = v, sum[x] = 1; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
		sum[x] = sum[x<<1] + sum[x<<1|1];
	}
	
	int get(int a, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return lx - (tree[x] >= a);
		int m = (lx + rx) >> 1;
		if(tree[x<<1|1] < a) return get(a, m+1, rx, x<<1|1);
		return get(a, lx, m, x<<1);
	}
	
	int get_s(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return sum[x];
		int m = (lx + rx) >> 1;
		return get_s(l, r, lx, m, x<<1) + get_s(l, r, m+1, rx, x<<1|1);
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	tree.init();
	int n, k; cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
		if(a[i] > b[i]) f[i] = 1, swap(a[i], b[i]);
	}
	
	for(int i=0;i<k;i++){
		cin>>t[i];
	}
	
	vector<int> p(n); iota(p.begin(), p.end(), 0);
	vector<int> q(k); iota(q.begin(), q.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j) { return (a[i] > a[j]); });
	sort(q.begin(), q.end(), [&](int i, int j) { return (t[i] > t[j]); });
	int j = 0;
	long long res = 0;
	for(auto i : p){
		while(j<k && t[q[j]] >= a[i]){
			tree.sett(q[j], t[q[j]]);
			j++;
		}
		
		//~ int s = 0, p;
		//~ for(p=k-1;~p;p--){
			//~ if(t[p] >= b[i]) s++;
			//~ if(a[i] <= t[p] && t[p] < b[i]){
				//~ break;
			//~ }
		//~ }
		
		int p = tree.get(b[i]);
		//~ assert(p1 == p);
		
		if(~p){
			int s = tree.get_s(p + 1, N);
			if(s&1) res += a[i];
			else res += b[i];
		} else {
			if(f[i]) swap(a[i], b[i]);
			
			if(j&1) res += b[i];
			else res += a[i];
		}
	}
	
	cout<<res<<"\n";
}

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