oj.uz

Submission #546730

# Submission time Handle Problem Language Result Execution time Memory
546730 2022-04-08T09:38:27 Z mosiashvililuka Fish (IOI08_fish) C++14
100 / 100
 537 ms 53440 KB 
#include<bits/stdc++.h>
using namespace std;
long long 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 <long long, long long> f[500009];
vector <pair <long long, long long> > v[500009];
void UPD(long long q, long long w){
	seg[za+q-1]=w+1;seg[za+q-1]%=mod;
	long long rr=za+q-1;rr/=2;
	while(rr!=0){
		seg[rr]=(seg[rr*2]*seg[rr*2+1])%mod;
		rr/=2;
	}
}
void read(long long q, long long w, long long 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,0LL))-v[f[i].second].begin();
		zx=v[f[i].second][c].first;
		d=lower_bound(f+1,f+a+1,make_pair(zx*2,0LL))-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;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 8 ms 11988 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12024 KB Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12124 KB Output is correct
2 Correct 208 ms 36100 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 8 ms 12244 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 24200 KB Output is correct
2 Correct 108 ms 25664 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12244 KB Output is correct
2 Correct 10 ms 12500 KB Output is correct
3 Correct 8 ms 12372 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 32920 KB Output is correct
2 Correct 204 ms 37644 KB Output is correct
3 Correct 210 ms 39028 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 39756 KB Output is correct
2 Correct 198 ms 40628 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 33664 KB Output is correct
2 Correct 222 ms 39076 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 38812 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 41612 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 34412 KB Output is correct
2 Correct 282 ms 41900 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 43452 KB Output is correct
2 Correct 284 ms 36520 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 42912 KB Output is correct
2 Correct 383 ms 45608 KB Output is correct
3 Correct 357 ms 44004 KB Output is correct
4 Correct 389 ms 53440 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 46388 KB Output is correct
2 Correct 444 ms 51504 KB Output is correct
3 Correct 495 ms 47664 KB Output is correct
4 Correct 537 ms 49356 KB Output is correct