Submission #1166817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166817		_rain_	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	35 / 100	137 ms	47952 KiB

fortune_telling2

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

const int N=(int)2e5;
const int MAXLOG=16;
vector<int>nen;
int a[N+2],b[N+2],t[N+2];
int n,k;

int Find(vector<int>&x,int val){
	return upper_bound(x.begin(),x.end(),val)-x.begin();
}

int rmq[N*3+2][MAXLOG+2],LOG[3*N+2];
struct Node{
	int pos,x,y;
	bool operator < (const Node&other) const{
		return pos>other.pos;
	}
};
int Getmax(int l,int r){
	if (l>r) return 0;
	int x=LOG[r-l+1];
	return max(rmq[l][x],rmq[r-(1<<x)+1][x]);
}

vector<Node>event;
int lim;
int bit[3*N+2];
	void add(int pos,int x){
		for(;pos<=lim;pos+=pos&-pos) bit[pos]+=x;
		return;
	}
	int Get(int pos){
		int sum=0;
		for(;pos;pos-=pos&-pos) sum+=bit[pos];
		return sum;
	}
	int sum_range(int l,int r){
		return Get(r)-Get(l-1);
	}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	
	//freopen("txt.inp","r",stdin);
	
	cin>>n>>k;
	lim=3*N;
	for(int i=1;i<=n;++i){
		cin>>a[i]>>b[i];
		nen.push_back(a[i]),
		nen.push_back(b[i]);
	}
	for(int i=1;i<=k;++i){
		cin>>t[i];
		nen.push_back(t[i]);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	
	for(int i=1;i<=n;++i){
		a[i]=Find(nen,a[i]),
		b[i]=Find(nen,b[i]);
	}
	for(int i=1;i<=k;++i) {
		t[i]=Find(nen,t[i]);
		rmq[t[i]][0]=max(rmq[t[i]][0],i);
	}
	
	for(int i=2;i<=lim;++i) LOG[i]=LOG[i/2]+1;
	for(int j=1;j<=MAXLOG;++j){
		for(int i=1;i+(1<<j)-1<=lim;++i){
			rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
		}
	}
	
	for(int i=1;i<=n;++i) {
		int mx=max(a[i],b[i]),mn=min(a[i],b[i]);
		int lastbit=Getmax(mn,mx-1);
		if (lastbit==0) event.push_back({lastbit,a[i],b[i]});
			else event.push_back({lastbit,mx,mn});
	}
	sort(event.begin(),event.end());
	
	int idx=k;
	LL ans=0;
	for(auto&x:event) {
		while (idx>=1 && idx>=x.pos){
			add(t[idx--],1);
		}
		int numflip=sum_range(x.x,lim);
//		cout<<x.pos<<' '<<nen[x.x-1]<<' '<<nen[x.y-1]<<' '<<numflip<<'\n';
		ans+=(numflip%2==0?nen[x.x-1]:nen[x.y-1]);
	}
	cout<<ans;
	
}

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