oj.uz

Submission #546727

# Submission time Handle Problem Language Result Execution time Memory
546727 2022-04-08T09:36:17 Z mosiashvililuka Fish (IOI08_fish) C++14
95 / 100
 600 ms 39628 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;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 7 ms 11988 KB Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 18284 KB Output is correct
2 Correct 101 ms 18940 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12120 KB Output is correct
2 Correct 12 ms 12244 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 22576 KB Output is correct
2 Correct 225 ms 25024 KB Output is correct
3 Correct 198 ms 32252 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 26168 KB Output is correct
2 Correct 194 ms 26396 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 22820 KB Output is correct
2 Correct 221 ms 25652 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 25580 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 27120 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 23648 KB Output is correct
2 Correct 306 ms 27980 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 29256 KB Output is correct
2 Correct 357 ms 25940 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 29644 KB Output is correct
2 Correct 373 ms 29772 KB Output is correct
3 Incorrect 352 ms 31068 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 31008 KB Output is correct
2 Correct 443 ms 39628 KB Output is correct
3 Correct 509 ms 37748 KB Output is correct
4 Correct 600 ms 36428 KB Output is correct