# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
53798 |
2018-07-01T08:11:52 Z |
김세빈(#1437) |
Fish (IOI08_fish) |
C++11 |
|
925 ms |
27944 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int T[1101010];
vector <int> V[505050];
int M[505050], K[505050], D[505050], C[505050];
pii F[505050];
int n, k, m, sz, ans;
void update(int p, int v)
{
p += sz;
T[p] = v;
for(p>>=1;p;p>>=1){
T[p] = (T[p<<1] * T[p<<1|1]) % m;
}
}
int get_mult(int l, int r)
{
int ret = 1;
l += sz, r += sz;
for(;l<r;){
if(l & 1) ret = (ret * T[l]) % m;
if(~r & 1) ret = (ret * T[r]) % m;
l = l+1 >> 1;
r = r-1 >> 1;
}
if(l == r) ret = (ret * T[l]) % m;
return ret;
}
bool comp(int ca, int cb) { return M[ca] < M[cb]; }
int main()
{
// freopen("input.txt","r",stdin);
int i, j, a, b;
int s, e, mid;
scanf("%d%d%d", &n, &k, &m);
for(i=0;i<n;i++){
scanf("%d%d", &a, &b); b--;
F[i] = pii(a, b);
V[b].push_back(a);
M[b] = max(M[b], a);
}
sort(F, F+n);
for(sz=1;sz<k;sz<<=1);
for(i=1;i<sz+k;i++) T[i] = 1;
for(i=0;i<k;i++) D[i] = i;
sort(D, D+k, comp);
for(i=0;i<k;i++) K[D[i]] = i;
for(i=j=0;i<n;i++){
for(;j<n && F[j].first * 2 <= F[i].first; j++){
C[F[j].second] ++;
update(K[F[j].second], C[F[j].second] + 1);
}
b = F[i].second;
if(F[i].first == M[b]){
for(s=K[b]+1,e=k-1;s<=e;){
mid = s+e >> 1;
if(upper_bound(V[b].begin(), V[b].end(), M[K[mid]]/2) - V[b].begin() <= C[b]) s = mid+1;
else e = mid-1;
}
update(K[b], 1);
ans = (ans + get_mult(0, s-1) + get_mult(0, K[b]) * C[b]) % m;
// printf("%d %d %d %d\n", b, s-1, get_mult(0, s-1), get_mult(0, K[b]) * C[b]);
update(K[b], C[b] + 1);
}
}
printf("%d\n",ans);
return 0;
}
Compilation message
fish.cpp: In function 'int get_mult(int, int)':
fish.cpp:31:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
l = l+1 >> 1;
~^~
fish.cpp:32:8: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
r = r-1 >> 1;
~^~
fish.cpp: In function 'int main()':
fish.cpp:77:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid = s+e >> 1;
~^~
fish.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &k, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
fish.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b); b--;
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12152 KB |
Output is 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 |
10 ms |
12336 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
12336 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
12412 KB |
Output is correct |
2 |
Incorrect |
12 ms |
12412 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12412 KB |
Output is correct |
2 |
Incorrect |
212 ms |
18996 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
12 ms |
18996 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
13 ms |
18996 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
115 ms |
18996 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
18996 KB |
Output is correct |
2 |
Incorrect |
15 ms |
18996 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
169 ms |
18996 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
287 ms |
19708 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
154 ms |
19708 KB |
Output is correct |
2 |
Incorrect |
281 ms |
19708 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
280 ms |
19708 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
371 ms |
20312 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
341 ms |
20312 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
690 ms |
25288 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
632 ms |
26384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
925 ms |
27944 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |