Submission #411268

#	Time	Username	Problem	Language	Result	Execution time	Memory
411268		wildturtle	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	2563 ms	124308 KiB

fortune_telling2

#include<bits/stdc++.h>
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l,x,BITree[3000006],tree[3000006],q,B[500005],idx,C[500005],fix[500005],ans;
pair <ll,ll> A[500005];
vector <ll> v,v1[500005];
map <ll,ll> mp,mp1;
void shekumshe(vector <ll> vc) {
	sort(vc.begin(),vc.end());
	x=1;
	mp[vc[0]]=x;
	mp1[x]=vc[0];
	for(ll i=1;i<vc.size();i++) {
		if(vc[i]!=vc[i-1]) x++;
		mp[vc[i]]=x;
		mp1[x]=vc[i];
	}
}
void update(ll node,ll le,ll ri,ll idx,ll val) {
	if(idx<le || ri<idx) return;
	if(le==ri) {
		tree[node]=max(tree[node],val); 
		return; 
	}
	update(2*node,le,(le+ri)/2,idx,val);
	update(2*node+1,(le+ri)/2+1,ri,idx,val);
	tree[node]=max(tree[2*node],tree[2*node+1]);
}
ll getmax(ll node,ll le,ll ri,ll start,ll end) {
	if(start>ri || le>end) return 0;
	if(start<=le && ri<=end) return tree[node];
	return max(getmax(2*node,le,(le+ri)/2,start,end),getmax(2*node+1,(le+ri)/2+1,ri,start,end));
}
void updateBIT(ll idx,ll val) {
	idx++;
	while(idx<=x) {
		BITree[idx]+=val;
		idx+=idx&(-idx);
	}
}
ll getSum(ll idx) {
	idx++;
	ll sum=0;
	while(idx>0) {
		sum+=BITree[idx];
		idx-=idx&(-idx);
	}
	return sum;
}
int main() {
	cin>>n>>q;
	for(ll i=1;i<=n;i++) {
		cin>>A[i].f>>A[i].sc;
		v.pb(A[i].f);
		v.pb(A[i].sc);
	}
	for(ll i=1;i<=q;i++) {
		cin>>B[i];
		v.pb(B[i]);
	}
	shekumshe(v);
	//cout<<endl;
	for(ll i=1;i<=n;i++) {
		A[i].f=mp[A[i].f];
		A[i].sc=mp[A[i].sc];
	//	cout<<A[i].f<<" "<<A[i].sc<<endl;
	}
	for(ll i=1;i<=q;i++) {
		B[i]=mp[B[i]];
	//	cout<<B[i]<<" ";
		update(1,1,x,B[i],i);
	}
	//cout<<endl;
	for(ll i=1;i<=n;i++) {
		if(A[i].f==A[i].sc) continue;
		idx=getmax(1,1,x,min(A[i].f,A[i].sc),max(A[i].f,A[i].sc)-1);
	//	cout<<idx<<" ";
		v1[idx].pb(i);
	}
	//cout<<endl<<endl;
	for(ll i=q;i>=1;i--) {
		//cout<<i<<"  ";
		for(ll j=0;j<v1[i].size();j++) {
			idx=v1[i][j];
		//	cout<<idx<<" ";
			C[idx]=(q-i)-getSum(max(A[idx].f,A[idx].sc)-1);
			fix[idx]=1;
		}
		//cout<<endl;
		updateBIT(B[i],1);
	}
	//cout<<endl;
	for(ll j=0;j<v1[0].size();j++) {
		idx=v1[i][j];
		C[idx]=q-getSum(max(A[idx].f,A[idx].sc)-1);
	}
	for(ll i=1;i<=n;i++) {
		A[i].f=mp1[A[i].f]; A[i].sc=mp1[A[i].sc];
		//cout<<A[i].f<<" "<<A[i].sc<<" "<<" "<<C[i]<<" "<<fix[i]<<" "<<ans<<endl;
		if(A[i].f==A[i].sc) { ans+=A[i].f; continue; }
		if(fix[i]==0 || A[i].f==max(A[i].f,A[i].sc)) {
			if(C[i]%2==1) ans+=A[i].sc;
			else ans+=A[i].f;
		}
		else {
			if(C[i]%2==1) ans+=A[i].f;
			else ans+=A[i].sc;
		}
		
	}
	cout<<ans;
}
/*
5 3
4 6
9 1
8 8
4 2
3 7
8
2
9
*/

Compilation message (stderr)

fortune_telling2.cpp: In function 'void shekumshe(std::vector<long long int>)':
fortune_telling2.cpp:16:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(ll i=1;i<vc.size();i++) {
      |             ~^~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:86:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(ll j=0;j<v1[i].size();j++) {
      |              ~^~~~~~~~~~~~~
fortune_telling2.cpp:96:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(ll j=0;j<v1[0].size();j++) {
      |             ~^~~~~~~~~~~~~

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