# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
53894 |
2018-07-01T15:06:25 Z |
Diuven |
Fish (IOI08_fish) |
C++11 |
|
3000 ms |
12128 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=2e9;
struct fish {
int len, col;
bool operator < (const fish &a) const {
return len<a.len;
}
} F[MX];
int n,k,mod;
struct seg {
static const int MX=1100000;
int n, tree[MX];
void init(int sz){
n=sz;
for(int i=1; i<MX; i++) tree[i]=1;
}
void upt(int v, int s, int e, int pos, int val){
if(pos<s || e<pos) return;
if(s==e){
tree[v]+=val;
return;
}
upt(v*2,s,(s+e)/2,pos,val);
upt(v*2+1,(s+e)/2+1,e,pos,val);
tree[v]=tree[v*2]*tree[v*2+1]%mod;
}
void upt(int pos, int val){
upt(1,1,n,pos,val);
}
int prod(int v, int s, int e, int l, int r){
if(r<s || e<l) return 1;
if(l<=s && e<=r) return tree[v];
return prod(v*2,s,(s+e)/2,l,r) * prod(v*2+1,(s+e)/2+1,e,l,r) % mod;
}
int prod(int l, int r){
if(r<l) return 1;
return prod(1,1,n,l,r);
}
} Tree;
int solve(){
int last[MX];
fill(last+1, last+k+1, 0);
for(int i=1; i<=n; i++){
last[F[i].col]=i;
}
bool calc[MX]={};
for(int i=1; i<=k; i++){
int x=last[i];
if(F[x].len*2<=F[n].len) continue;
calc[last[i]]=true;
}
int ans=0;
int cnt[MX]={};
Tree.init(k);
for(int i=1, pos=0; i<=n; i++){
if(!calc[i]) continue;
int c=F[i].col;
while(pos<n && F[pos+1].len*2<=F[i].len){
pos++;
cnt[F[pos].col]++;
// Tree.upt(F[pos].col,1);
}
if(i==n) cnt[c]++;
int now=1;
for(int j=1; j<=k; j++){
if(i!=n && j==c) continue;
now=(now*(cnt[j]+1))%mod;
}
if(i==n) now=(now+mod-1)%mod;
/*
if(i==n) now=(Tree.prod(1,k)+mod-1)%mod;
else now=Tree.prod(1,c-1) * Tree.prod(c+1, k) % mod;
*/
// cout<<i<<' '<<F[i].len<<' '<<F[i].col<<": "<<now<<'\n';
ans=(ans+now)%mod;
}
return ans;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>k>>mod;
for(int i=1; i<=n; i++)
cin>>F[i].len>>F[i].col;
sort(F+1, F+n+1);
cout<<solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
7160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
7272 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
7272 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
7272 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7340 KB |
Output is correct |
2 |
Incorrect |
7 ms |
7348 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7348 KB |
Output is correct |
2 |
Incorrect |
186 ms |
11156 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
11156 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
11156 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
68 ms |
11156 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
11156 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
129 ms |
11156 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
160 ms |
11216 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
209 ms |
11216 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1810 ms |
11216 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3050 ms |
11356 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3048 ms |
11356 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3060 ms |
11388 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3049 ms |
11480 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3030 ms |
12128 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |