Submission #109204

#	Time	Username	Problem	Language	Result	Execution time	Memory
109204		maruii	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	774 ms	69196 KiB

fortune_telling2

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

const int SIZE = 1<<19;
struct ST{
	int data[2*SIZE];
	void update(int x, int v){
		for(x+=SIZE; x; x>>=1) data[x] = max(data[x], v);
	}
	int query(int s, int e){
		int ret = 0;
		for(s+=SIZE, e+=SIZE; s<=e; s>>=1, e>>=1){
			if( s&1) ret = max(ret, data[s++]);
			if(~e&1) ret = max(ret, data[e--]);
		}
		return ret;
	}
} seg;
struct PST{
	struct Node{
		int l,r;
		bool v;
	} node[20*SIZE];
	int cnt;
	int init(int s, int e){
		int nn = cnt++;
		if(s==e) return nn;
		int m = s+e>>1;
		node[nn].l = init(s, m), node[nn].r = init(m+1, e);
		return nn;
	}
	int update(int bef, int ns, int ne, int x){
		if(ns>x || ne<x) return bef;
		int nn = cnt++;
		auto &cur = node[nn];
		if(ns==ne){
			cur = node[bef];
			cur.v ^= 1;
			return nn;
		}
		int m = ns+ne>>1;
		cur.l = update(node[bef].l, ns, m, x), cur.r = update(node[bef].r, m+1, ne, x);
		cur.v = node[cur.l].v ^ node[cur.r].v;
		return nn;
	}
	bool query(int nn, int ns, int ne, int s, int e){
		if(ns>e || ne<s) return 0;
		auto &cur = node[nn];
		if(s<=ns && ne<=e) return cur.v;
		int m = ns+ne>>1;
		return query(cur.l, ns, m, s, e) ^ query(cur.r, m+1, ne, s, e);
	}
} pst;
int root[200002], A[200001], B[200001], T[200001];
vector<int> xx;
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, K; cin>>N>>K;
	for(int i=0; i<N; ++i) cin>>A[i]>>B[i], xx.push_back(A[i]), xx.push_back(B[i]);
	for(int i=1; i<=K; ++i) cin>>T[i];
	sort(xx.begin(), xx.end()), xx.erase(unique(xx.begin(), xx.end()), xx.end());
	for(int i=0; i<N; ++i){
		A[i] = lower_bound(xx.begin(), xx.end(), A[i]) - xx.begin() + 1;
		B[i] = lower_bound(xx.begin(), xx.end(), B[i]) - xx.begin() + 1;
	}
	root[K+1] = pst.init(0, xx.size());
	for(int i=K; i; --i){
		T[i] = upper_bound(xx.begin(), xx.end(), T[i]) - xx.begin();
		seg.update(T[i], i);
		root[i] = pst.update(root[i+1], 0, xx.size(), T[i]);
	}
	long long ans = 0;
	for(int i=0; i<N; ++i){
		int a=A[i], b=B[i];
		if(a>b) swap(a, b);
		int t = seg.query(a, b-1), s = pst.query(root[t+1], 0, xx.size(), b, xx.size());
		if(t && s) ans += xx[a-1];
		else if(t) ans += xx[b-1];
		else if(s) ans += xx[B[i]-1];
		else ans += xx[A[i]-1];
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'int PST::init(int, int)':
fortune_telling2.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e>>1;
           ~^~
fortune_telling2.cpp: In member function 'int PST::update(int, int, int, int)':
fortune_telling2.cpp:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = ns+ne>>1;
           ~~^~~
fortune_telling2.cpp: In member function 'bool PST::query(int, int, int, int, int)':
fortune_telling2.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = ns+ne>>1;
           ~~^~~

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