# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
53835 |
2018-07-01T09:10:52 Z |
노영훈(#1436) |
Fish (IOI08_fish) |
C++11 |
|
520 ms |
47196 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=2e9;
int mod;
int n, k;
struct fish {
int l, c;
bool operator < (const fish &f) const {
return l<f.l;
}
} F[MX];
int pw(int a, int e){
if(e==0) return 1;
int t=pw(a,e/2); t=t*t%mod;
return (e%2==1 ? t*a%mod : t);
}
int inv(int x){
return pw(x,mod-2);
}
vector<int> P[MX];
uint16_t D[MX], E[MX];
void init(){
// includes empty
D[1]=2;
for(int i=2; i<=n; i++){
int c=F[i].c;
int cnt=upper_bound(P[c].begin(), P[c].end(), i-1)-P[c].begin();
if(cnt==0) D[i]=(D[i-1]*2)%mod;
else D[i]=(D[i-1]+D[i-1]*inv(cnt+1))%mod;
}
}
int find(int x){
int s=0, e=n;
while(s<e){
int m=(s+e+1)/2;
if(F[m].l*2<=x) s=m;
else e=m-1;
}
return s;
}
int get(int i){
int r=find(F[i].l);
int c=F[i].c;
int cnt=upper_bound(P[c].begin(), P[c].end(), r)-P[c].begin();
if(cnt==0) return D[r]*2%mod;
else return 1LL*D[r]*inv(cnt+1)%mod;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>k>>mod;
for(int i=1; i<=n; i++){
int l,c; cin>>l>>c;
F[i]={l,c};
}
sort(F+1, F+n+1);
for(int i=1; i<=n; i++)
P[F[i].c].push_back(i);
init();
bool done[30010]={};
int ans=0;
for(int i=n; i>=1; i--){
if(F[i].l*2<=F[n].l) continue;
if(done[F[i].c]) continue;
done[F[i].c]=true;
ans=(ans+get(i))%mod;
}
cout<<(ans+mod-1)%mod;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
12152 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
12260 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
12260 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
12260 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
12260 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
12368 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
12 ms |
12368 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
12368 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
139 ms |
15556 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
12 ms |
15556 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
248 ms |
17232 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
361 ms |
20404 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
222 ms |
20404 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
391 ms |
20404 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
430 ms |
20564 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
329 ms |
37740 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
385 ms |
43648 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
355 ms |
45472 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
520 ms |
47196 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |