oj.uz

Submission #546716

# Submission time Handle Problem Language Result Execution time Memory
546716 2022-04-08T09:14:15 Z mosiashvililuka Fish (IOI08_fish) C++14
88 / 100
 559 ms 46836 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;
	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 6 ms 11988 KB Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12108 KB Output is correct
2 Correct 7 ms 12084 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 198 ms 30592 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 20708 KB Output is correct
2 Correct 114 ms 22156 KB Output is correct

Subtask #10
6.0 / 6.0

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

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 26652 KB Output is correct
2 Incorrect 217 ms 31600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 32284 KB Output is correct
2 Correct 211 ms 33400 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 27208 KB Output is correct
2 Correct 197 ms 32700 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 31892 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 34508 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 29816 KB Output is correct
2 Correct 288 ms 35812 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 36496 KB Output is correct
2 Correct 303 ms 30652 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 34920 KB Output is correct
2 Correct 377 ms 37604 KB Output is correct
3 Incorrect 336 ms 37792 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 465 ms 39016 KB Output is correct
2 Correct 484 ms 46836 KB Output is correct
3 Correct 520 ms 45896 KB Output is correct
4 Correct 559 ms 44460 KB Output is correct