Submission #255862

#	Time	Username	Problem	Language	Result	Execution time	Memory
255862		oolimry	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	362 ms	19420 KiB

fortune_telling2

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int,int> ii;

ii arr[200005];
int changes[200005];

struct segmax{
	int tree[1200000];
	int n;
	
	void init(int N){
		n = N;
		fill(tree,tree+2*n,-1);
	}
	
	void update(int i, int x){
		for(i += n;i > 0;i >>= 1) tree[i] = max(tree[i], x);
	}
	
	int query(int l, int r){
		int res = -1;
		for(l += n, r += n;l < r;l >>= 1, r >>= 1){
			if(l&1) res = max(res, tree[l++]);
			if(r&1) res = max(res, tree[--r]);
		}
		return res;
	}
} RMAX;


struct segxor{
	bitset<400005> tree;
	int n;
	
	void init(int N){
		n = N;
	}
	
	void update(int i){
		for(i += n;i > 0;i >>= 1) tree[i] = !tree[i];
	}
	
	int query(int l, int r){
		if(l == -1) l = 0;
		int res = 0;
		for(l += n, r += n;l < r;l >>= 1, r >>= 1){
			if(l&1) res ^= tree[l++];
			if(r&1) res ^= tree[--r];
		}
		return res;
	}
} RXOR;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, Q; cin >> n >> Q;
	
	vector<int> dis;
	for(int i = 0;i < n;i++){
		int a, b; cin >> a >> b;
		arr[i] = ii(a,b);
		dis.push_back(a);
		dis.push_back(b);
	}
	
	for(int i = 0;i < Q;i++){
		int x; cin >> x;
		changes[i] = x;
		dis.push_back(x);
	}
	
	sort(all(dis));
	dis.erase(unique(all(dis)), dis.end());
	
	for(int i = 0;i < n;i++){
		arr[i].first = lower_bound(all(dis), arr[i].first) - dis.begin();
		arr[i].second = lower_bound(all(dis), arr[i].second) - dis.begin();
	}
	for(int i = 0;i < Q;i++){
		changes[i] = lower_bound(all(dis), changes[i]) - dis.begin();
	}
	
	RMAX.init(sz(dis));
	for(int i = 0;i < Q;i++){
		RMAX.update(changes[i], i);
	}
	
	long long ans = 0;
	
	vector<ii> updates;
	for(int i = 0;i < Q;i++) updates.push_back(ii(changes[i], i));
	sort(all(updates));
	
	sort(arr,arr+n,[&](ii a, ii b){ return max(a.first,a.second) > max(b.first,b.second); });
	
	RXOR.init(Q);
	for(int i = 0;i < n;i++){
		int L = arr[i].first, R = arr[i].second;
		if(L > R) swap(L,R);
		
		while(!updates.empty()){
			ii top = updates.back();
			if(top.first < R) break;
			RXOR.update(top.second);
			updates.pop_back();
		}
		
		int T = RMAX.query(L, R); ///latest flip which forces it to become R value
		int after = RXOR.query(T, Q);
				
		if(T != -1){ ///was flipped to max at some point
			if(after == 0) ans += dis[R];
			else ans += dis[L];
		}
		else{
			if(after == 0) ans += dis[arr[i].first];
			else ans += dis[arr[i].second];
		}
		
	}
	cout << ans;
}

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