oj.uz

답안 #880458

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
880458 2023-11-29T12:59:40 Z josanneo22 Fish (IOI08_fish) C++17
38 / 100
 313 ms 37852 KB 
#include<bits/stdc++.h>
using namespace std;

#define ls p<<1
#define rs p<<1|1
const int N=2e5+500;
int t[N<<2],F,K,M,cnt[N],f[N];
set<int> S[N];
void modify(int p,int l,int r,int x,int v){
	if(l==r){
		t[p]=v%M;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) modify(ls,l,mid,x,v);
	if(x>=mid+1) modify(rs,mid+1,r,x,v);
	t[p]=(t[ls]*t[rs])%M;
	return;
}
int query(int p,int l,int r,int ql,int qr){
	if(ql<=l && r<=qr) return t[p];
	int mid=(l+r)>>1,ans=1;
	if(ql<=mid) ans*=query(ls,l,mid,ql,qr);
	if(qr>=mid+1) ans*=query(rs,mid+1,r,ql,qr);
	return ans%M;
}
struct fish{
	int len,gem;
	bool operator <(const fish &b){ return len<b.len;}
}a[N];

int main(){
	cin>>F>>K>>M;
	for(int i=1;i<=F;i++)
		cin>>a[i].len>>a[i].gem;
	sort(a+1,a+1+F);
	int T=K;
	for(int i=F;i>=1;i--){
		if(!cnt[a[i].gem])
			cnt[a[i].gem]=T--;
		a[i].gem=cnt[a[i].gem];
	}
	for(int i=1;i<=F;i++) cnt[i]=0;
	for(int i=1;i<=F;i++){
		cnt[a[i].gem]++;
		S[a[i].gem].insert(i);
	}
	for(int i=1;i<=K;i++) cnt[i]++;
	for(int i=1;i<=K;i++) modify(1,1,K,i,cnt[i]);
	int ans=0;
	for(int i=F,j=F;i>=1;i--){
		if(*prev(S[a[i].gem].end())==i){
			while(j>=1 && a[j].len*2>a[i].len){
				int gem=a[j].gem;
				--cnt[gem]; modify(1,1,K,gem,cnt[gem]);
				j--;
			}
			int gem=a[i].gem;
			f[gem]=j;
			int x=*S[gem].upper_bound(f[gem]),l=gem,r=K,res=K;
			while(l<=r){
				int mid=(l+r)>>1;
				if(f[mid]<x) res=mid,l=mid+1;
				else r=mid-1;
			}
			int before=(gem==1?1:query(1,1,K,1,gem-1));
			int after=(gem==res?1:query(1,1,K,gem+1,res))+(cnt[gem]-1);
			ans+=before*after; ans%=M;
		}
	}
	cout<<ans<<'\n';
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14812 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14684 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14684 KB Output is correct
2 Runtime error 263 ms 35940 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14680 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 14940 KB Output is correct

Subtask #9
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 27048 KB Output is correct
2 Runtime error 141 ms 32992 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 7 ms 15040 KB Output is correct
3 Correct 6 ms 14940 KB Output is correct

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 168 ms 33900 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 253 ms 36180 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 174 ms 34128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 249 ms 36140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 283 ms 37484 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 220 ms 36060 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 274 ms 36928 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 205 ms 35124 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 313 ms 37852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -