Submission #546732

#	Time	Username	Problem	Language	Result	Execution time	Memory
546732		mosiashvililuka	Fish (IOI08_fish)	C++14	100 / 100	513 ms	39600 KiB

fish

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,K,mod,MX[500009],seg[2000009],val[500009],za,l,r,z,pas,I;
pair <int, int> f[500009];
vector <pair <int, int> > v[500009];
void UPD(int q, int w){
	seg[za+q-1]=w+1;seg[za+q-1]%=mod;
	int rr=za+q-1;rr/=2;
	while(rr!=0){
		seg[rr]=(seg[rr*2]*seg[rr*2+1])%mod;
		rr/=2;
	}
}
void read(int q, int w, int rr){
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		z=z*seg[rr];z%=mod;
		return;
	}
	read(q,(q+w)/2,rr*2);
	read((q+w)/2+1,w,rr*2+1);
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>K>>mod;
	for(i=1; i<=a; i++){
		cin>>f[i].first>>f[i].second;
	}
	za=1;
	while(za<a) za*=2;
	for(i=0; i<=za*2; i++) seg[i]=1;
	sort(f+1,f+a+1);
	for(i=1; i<=a; i++) MX[f[i].second]=i;
	for(i=1; i<=a; i++){
		v[f[i].second].push_back({f[i].first,i});
	}
	I=1;
	for(i=1; i<=a; i++){
		/*val[MX[f[i].second]]++;
		UPD(MX[f[i].second],val[MX[f[i].second]]);*/
		while(I<=a&&f[I].first<=f[i].first/2){
			val[MX[f[I].second]]++;
			UPD(MX[f[I].second],val[MX[f[I].second]]);
			I++;
		}
		if(MX[f[i].second]!=i){
			continue;
		}
		c=lower_bound(v[f[i].second].begin(),v[f[i].second].end(),make_pair(f[i].first/2+1,0))-v[f[i].second].begin();
		zx=v[f[i].second][c].first;
		d=lower_bound(f+1,f+a+1,make_pair(zx*2,0))-f;
		j=d-1;
		//didebs arcerts ar vigebt sashualoebs vigebt (n+1) qva i feris
		zx=1;
		l=1;r=i-1;z=1;
		if(l<=r){
			read(1,za,1);
			//cout<<z<<"\n";
			zx*=z;zx%=mod;
		}
		l=i+1;r=j;z=1;
		if(l<=r){
			read(1,za,1);
			//cout<<z<<"\n";
			zx*=z;zx%=mod;
		}
		//cout<<zx<<"\n";
		pas+=zx;pas%=mod;
		//cout<<pas<<"\n";
		//cota qvas vigebt (n+1)ze da arc sashualoebs arc didebs ar vigebt
		zx=1;
		l=1;r=i-1;z=1;
		if(l<=r){
			read(1,za,1);
			zx*=z;zx%=mod;
		}
		zx*=/*(val[MX[f[i].second]]-1)*/c%mod;zx%=mod;
		pas+=zx;pas%=mod;
		//
		//cout<<i<<" "<<c+1<<" "<<j<<" "<<pas<<"\n";
	}
	cout<<pas;
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5