Submission #707089

#	Time	Username	Problem	Language	Result	Execution time	Memory
707089		amirhoseinfar1385	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	941 ms	45240 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<pair<int,int>>all;
vector<int>allm;
int kaf=(1<<18);
struct segment
{
	struct node{
		vector<int>v;
	};
	node seg[(1<<19)];
	void upd(int i,int w){
		if(i==0){
			return ;
		}
		seg[i].v.push_back(w);
		return upd((i>>1),w);
	}
	void pre(){
		for(int i=0;i<(1<<19);i++){
			sort(seg[i].v.begin(),seg[i].v.end());
		}
	}
	int porsakh(int i,int l,int r,int tl,int tr,int hadl,int hadr){
		if(l>r||l>tr||r<tl){
			return -1;
		}
		int p=lower_bound(seg[i].v.begin(),seg[i].v.end(),hadl)-seg[i].v.begin();
		int pp=upper_bound(seg[i].v.begin(),seg[i].v.end(),hadr)-seg[i].v.begin();
		if(p==pp){
			return -1;
		}	
		if(l==r){
			return l;
		}	
		int m=(l+r)>>1;
		int ret=porsakh((i<<1)^1,m+1,r,tl,tr,hadl,hadr);
		if(ret==-1){
			ret=porsakh((i<<1),l,m,tl,tr,hadl,hadr);
		}
		return ret;
	}
	int porsted(int i,int l,int r,int tl,int tr,int hadl,int hadr){
		if(l>r||l>tr||r<tl){
			return 0;
		}
		if(l>=tl&&r<=tr){
			int p=lower_bound(seg[i].v.begin(),seg[i].v.end(),hadl)-seg[i].v.begin();
			int pp=upper_bound(seg[i].v.begin(),seg[i].v.end(),hadr)-seg[i].v.begin();
			return pp-p;	
		}
		int m=(l+r)>>1;
		int ret=porsted((i<<1)^1,m+1,r,tl,tr,hadl,hadr);
		ret+=porsted((i<<1),l,m,tl,tr,hadl,hadr);
		return ret;
	}
};
segment seg;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	all.resize(n);
	allm.resize(m);
	for(int i=0;i<n;i++){
		cin>>all[i].first>>all[i].second;
	}
	for(int i=0;i<m;i++){
		cin>>allm[i];
		seg.upd(kaf+i,allm[i]);
	}
	seg.pre();
	long long res=0;
	for(int i=0;i<n;i++){
		int lasta=seg.porsakh(1,0,kaf-1,0,m+1,min(all[i].first,all[i].second),max(all[i].first,all[i].second)-1);
		int ted=seg.porsted(1,0,kaf-1,lasta+1,m+1,max(all[i].first,all[i].second),1e9+5);
		//cout<<i<<" "<<lasta<<" "<<ted<<"\n";
		if(lasta==-1){
			if(ted&1){
				res+=all[i].second;
			}
			else{
				res+=all[i].first;
			}
		}
		else{
			if(ted&1){
				res+=min(all[i].first,all[i].second);
			}
			else{
				res+=max(all[i].first,all[i].second);
			}
		}
	}
	cout<<res<<'\n';
}

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