Submission #917700

#	Time	Username	Problem	Language	Result	Execution time	Memory
917700		PM1	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	636 ms	60876 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
const int mxn=2e5+5,sz=(1<<20);
int n,q,a[mxn],b[mxn],qu[mxn];
long long int ans=0;
struct segment{
	vector<int>v[sz];
	void build(int id,int L,int R){
		if(L+1==R){
			v[id].push_back(qu[L]);
			return ;
		}
		int mid=(L+R)/2;
		build(id*2,L,mid);
		build(id*2+1,mid,R);
		for(auto i:v[id*2])
			v[id].push_back(i);
		for(auto i:v[id*2+1])
			v[id].push_back(i);
		sort(v[id].begin(),v[id].end());
	}
	int get(int id,int L,int R,int l,int r){
		if(L+1==R)
			return L;
		int mid=(L+R)/2;
		int x=lower_bound(v[id].begin(),v[id].end(),l)-v[id].begin();
		if(x==v[id].size() || v[id][x]>=r)
			return 0;
		x=lower_bound(v[id*2+1].begin(),v[id*2+1].end(),l)-v[id*2+1].begin();
		if(x==v[id*2+1].size() || v[id*2+1][x]>=r)
			return get(id*2,L,mid,l,r);
		else
			return get(id*2+1,mid,R,l,r);
	}
	int pet(int id,int L,int R,int l,int r,int x){
		if(L==l && R==r){
			int res=lower_bound(v[id].begin(),v[id].end(),x)-v[id].begin();
			return v[id].size()-res;
		}
		int mid=(L+R)/2,res=0;
		if(l<mid)
			res+=pet(id*2,L,mid,l,min(r,mid),x);
		if(r>mid)
			res+=pet(id*2+1,mid,R,max(l,mid),r,x);
		return res;
	}
}seg;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	for(int i=1;i<=q;i++){
		cin>>qu[i];
	}
	seg.build(1,1,q+1);
	for(int i=1;i<=n;i++){
		 int x=min(a[i],b[i]);
		 int y=max(a[i],b[i]);
		 int l=seg.get(1,1,q+1,x,y);
		 int num=(l!=q)?seg.pet(1,1,q+1,l+1,q+1,y):0;
		 if(l==0)
		 	ans+=(num&1)?b[i]:a[i];
		 else{
		 	if(a[i]<b[i])
		 		ans+=(num&1)?a[i]:b[i];
		 	else
		 		ans+=(num&1)?b[i]:a[i];
		 }
		// cout<<ans<<" ";
	}
	cout<<ans<<endl;
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'int segment::get(int, int, int, int, int)':
fortune_telling2.cpp:27:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   if(x==v[id].size() || v[id][x]>=r)
      |      ~^~~~~~~~~~~~~~
fortune_telling2.cpp:30:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   if(x==v[id*2+1].size() || v[id*2+1][x]>=r)
      |      ~^~~~~~~~~~~~~~~~~~

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