Submission #714777

#	Time	Username	Problem	Language	Result	Execution time	Memory
714777		dsyz	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	312 ms	33872 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
bool cmp(pair<ll,ll> a,pair<ll,ll> b){
	return max(a.first,a.second) > max(b.first,b.second);
}

ll fw[MAXN];
void upd(int x,ll nval) {
    for(;x<MAXN;x+=x&(-x)) fw[x]+=nval;
}
ll query(int x) {
    ll res = 0;
    for(;x;x-=x&(-x)) res += fw[x];
    return res;
}
ll sum(int a,int b) {
    return query(b) - query(a-1);
}

struct node{
	int s, e, m;
	int val;
	node *l, *r; 
	node (int S, int E){
		s = S, e = E, m = (s+e)/2;
		val = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void update(int X, int V){ 
		if(s == e) val = V;
		else{
			if(X <= m) l->update(X, V);
			else r->update(X, V);
			val = max(l->val,r->val);
		}
	}
	int query(int S, int E){
		if(s == S && e == E) return val;
		else if(E <= m) return l->query(S, E);
		else if(S >= m+1) return r->query(S, E);
		else return max(l->query(S, m),r->query(m+1, E)); 
	}
} *root;

int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,K;
	cin>>N>>K;
	root = new node(0,K - 1);
	vector<pair<ll,ll> > c;
	vector<pair<ll,ll> > q;
	for(ll i = 0;i < N;i++){
		ll a,b;
		cin>>a>>b;
		c.push_back({a,b});	
	}
	for(ll i = 0;i < K;i++){
		ll t;
		cin>>t;
		q.push_back({t,i});
	}
	sort(c.begin(),c.end(),cmp);
	sort(q.begin(),q.end());
	for(ll i = 0;i < K;i++){
		root -> update(i,q[i].second);
	}
	ll index = K - 1;
	ll ans = 0;
	for(auto u : c){
		ll a = u.first;
		ll b = u.second;
		while(index >= 0 && q[index].first >= max(a,b)){
			upd(q[index].second + 1,1);
			index--;
		}
		ll low = lower_bound(q.begin(),q.end(),make_pair(min(a,b),0ll)) - q.begin();
		ll high = lower_bound(q.begin(),q.end(),make_pair(max(a,b),0ll)) - q.begin();
		ll s = -1;
		if(low <= high - 1){
			s = root -> query(low,high - 1);
		}
		ll num = sum(max(1ll,s + 1),K);
		if(s == -1 && b > a) num++;
		if(num % 2 == 0) ans += max(a,b);
		else ans += min(a,b);
	}
	cout<<ans<<'\n';
}

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