# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
53815 |
2018-07-01T08:49:19 Z |
김세빈(#1437) |
Fish (IOI08_fish) |
C++11 |
|
1070 ms |
52248 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];
bool chk[505050];
pii F[505050];
int n, k, m, sz, ans;
void update(int p, int v)
{
p += sz;
T[p] = v % m;
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()
{
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);
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=0;i<n;i++){
V[F[i].second].push_back(F[i].first);
}
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] && !chk[b]){
chk[b] = 1;
for(s=K[b]+1,e=k-1;s<=e;){
mid = s+e >> 1;
if(upper_bound(V[b].begin(), V[b].end(), M[D[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) + C[b] % m * get_mult(0, K[b])) % m;
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:32:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
l = l+1 >> 1;
~^~
fish.cpp:33:8: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
r = r-1 >> 1;
~^~
fish.cpp: In function 'int main()':
fish.cpp:80:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid = s+e >> 1;
~^~
fish.cpp:47: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:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b); b--;
~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
12280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
12280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
12448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
12448 KB |
Output is correct |
2 |
Correct |
14 ms |
12448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12448 KB |
Output is correct |
2 |
Correct |
206 ms |
18960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
18960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
18960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
95 ms |
18960 KB |
Output is correct |
2 |
Correct |
123 ms |
18960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
18960 KB |
Output is correct |
2 |
Correct |
15 ms |
18960 KB |
Output is correct |
3 |
Correct |
18 ms |
18960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
202 ms |
18960 KB |
Output is correct |
2 |
Correct |
266 ms |
18960 KB |
Output is correct |
3 |
Correct |
249 ms |
19260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
242 ms |
19412 KB |
Output is correct |
2 |
Correct |
274 ms |
19740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
167 ms |
19740 KB |
Output is correct |
2 |
Correct |
331 ms |
19740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
279 ms |
19740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
319 ms |
20336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
259 ms |
20336 KB |
Output is correct |
2 |
Correct |
420 ms |
23488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
630 ms |
25456 KB |
Output is correct |
2 |
Correct |
446 ms |
25456 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
505 ms |
26376 KB |
Output is correct |
2 |
Correct |
547 ms |
26376 KB |
Output is correct |
3 |
Correct |
593 ms |
29052 KB |
Output is correct |
4 |
Correct |
562 ms |
31768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
816 ms |
35720 KB |
Output is correct |
2 |
Correct |
836 ms |
52248 KB |
Output is correct |
3 |
Correct |
1055 ms |
52248 KB |
Output is correct |
4 |
Correct |
1070 ms |
52248 KB |
Output is correct |