Submission #960401

#	Time	Username	Problem	Language	Result	Execution time	Memory
960401		pcc	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	419 ms	74036 KiB

fortune_telling2

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define _all(T) T.begin(),T.end()

const int mxn = 6e5+10;
int N,Q;
vector<int> all;
int rp[mxn];
pii range[mxn];
int arr[mxn];
bitset<mxn> flop;

namespace C1{
	vector<pii> bit[mxn];
	void add(int p,pii v){
		for(;p<mxn;p+=p&-p){
			bit[p].push_back(v);
		}
		return;
	}
	void getval(int p,int id){
		for(int i = p;i>0;i-= i&-i){
			while(!bit[i].empty()&&bit[i].back().fs>=p){
				int now = bit[i].back().sc;bit[i].pop_back();
				rp[now] = max(rp[now],id);
			}
		}
		return;
	}
	void GO(){
		for(int i = 1;i<=N;i++){
			if(range[i].fs == range[i].sc)continue;
			add(range[i].fs,pii(range[i].sc-1,i));
		}
		for(int i = 1;i<mxn;i++)sort(bit[i].begin(),bit[i].end());
		for(int i = Q;i>=1;i--){
			getval(arr[i],i);
		}
		//for(int i = 1;i<=N;i++)cout<<rp[i]<<' ';cout<<endl;
		return;
	}
}

namespace C2{
	ll ans = 0;
	int bit[mxn];
	void modify(int p,int v){
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;
	}
	int getval(int s,int e){
		int re = 0;
		for(;e>0;e-= e&-e)re += bit[e];
		s--;
		for(;s>0;s-= s&-s)re -= bit[s];
		return re;
	}
	vector<int> op[mxn];
	void GO(){
		ans = 0;
		for(int i = 1;i<=N;i++){
			op[rp[i]].push_back(i);
		}
		for(int i = Q;i>=1;i--){
			modify(arr[i],1);
			for(auto &j:op[i]){
				int cnt = getval(range[j].sc,mxn-1);
				if(cnt&1)ans += all[range[j].fs];
				else ans += all[range[j].sc];
			}
		}
		for(auto &j:op[0]){
			int cnt = getval(range[j].sc,mxn-1);
			if(flop[j])swap(range[j].fs,range[j].sc);
			if(cnt&1)ans += all[range[j].sc];
			else ans += all[range[j].fs];
		}
		cout<<ans<<'\n';
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	all.push_back(-1);
	for(int i = 1;i<=N;i++){
		cin>>range[i].fs>>range[i].sc;
		if(range[i].fs>range[i].sc){
			flop[i] = true;
			swap(range[i].fs,range[i].sc);
		}
		all.push_back(range[i].fs);
		all.push_back(range[i].sc);
	}
	for(int i = 1;i<=Q;i++){
		cin>>arr[i];
		all.push_back(arr[i]);
	}
	sort(all.begin(),all.end());all.resize(unique(all.begin(),all.end())-all.begin());
	for(int i = 1;i<=N;i++){
		range[i].fs = lower_bound(_all(all),range[i].fs)-all.begin();
		range[i].sc = lower_bound(_all(all),range[i].sc)-all.begin();
	}
	for(int i = 1;i<=Q;i++)arr[i] = lower_bound(_all(all),arr[i])-all.begin();
	C1::GO();
	C2::GO();
}

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