oj.uz

Submission #546732

# Submission time Handle Problem Language Result Execution time Memory
546732 2022-04-08T09:42:05 Z mosiashvililuka Fish (IOI08_fish) C++14
100 / 100
 513 ms 39600 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12052 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 6 ms 12116 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 172 ms 24516 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12116 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12116 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 18260 KB Output is correct
2 Correct 97 ms 19020 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12152 KB Output is correct
2 Correct 10 ms 12228 KB Output is correct
3 Correct 9 ms 12244 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 22596 KB Output is correct
2 Correct 195 ms 24928 KB Output is correct
3 Correct 183 ms 25544 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 26144 KB Output is correct
2 Correct 186 ms 26400 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 22892 KB Output is correct
2 Correct 211 ms 25620 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 25680 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 27124 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 23524 KB Output is correct
2 Correct 253 ms 27976 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 29284 KB Output is correct
2 Correct 258 ms 25944 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 29672 KB Output is correct
2 Correct 317 ms 29888 KB Output is correct
3 Correct 320 ms 31160 KB Output is correct
4 Correct 319 ms 29940 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 31060 KB Output is correct
2 Correct 453 ms 39600 KB Output is correct
3 Correct 488 ms 37708 KB Output is correct
4 Correct 513 ms 36420 KB Output is correct