# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
53794 |
2018-07-01T08:01:19 Z |
강태규(#1435) |
Fish (IOI08_fish) |
C++11 |
|
901 ms |
11020 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
const int inf = 1e9 + 1;
int f, k, mod;
pii fs[500000];
int mx[500001];
int cnt[500001];
int ch[500001];
int seg1[1 << 20];
int seg2[1 << 20];
void update(int seg[], int i, int s, int e, int x, int v) {
if (s == e) {
seg[i] = (v + 1) % mod;
return;
}
int m = (s + e) / 2;
if (x <= m) update(seg, i << 1, s, m, x, v);
else update(seg, i << 1 | 1, m + 1, e, x, v);
seg[i] = seg[i << 1] * seg[i << 1 | 1] % mod;
}
int main() {
scanf("%d%d%d", &f, &k, &mod);
for (int i = 0; i < f; ++i) {
int l, x;
scanf("%d%d", &l, &x);
fs[i] = pii(l, x);
++cnt[x];
}
for (int i = 1; i <= k; ++i) {
update(seg1, 1, 1, k, i, cnt[i]);
update(seg2, 1, 1, k, i, cnt[i]);
}
sort(fs, fs + f, greater<pii>());
int ans = 0;
for (int i = 0, j = 0; i < f; ++i) {
if (ch[fs[i].second]) continue;
while (j < f && 2 * fs[j].first > fs[i].first) {
--cnt[fs[j].second];
update(seg1, 1, 1, k, fs[j].second, cnt[fs[j].second]);
if (ch[fs[j].second] == 0)
update(seg2, 1, 1, k, fs[j].second, cnt[fs[j].second]);
++j;
}
ans += seg2[1];
ans %= mod;
ch[fs[i].second] = 1;
update(seg2, 1, 1, k, fs[i].second, 0);
if (i == 0) {
for (int it = 1; it <= k; ++it) mx[it] = cnt[it];
}
else {
if (cnt[fs[i].second] == mx[fs[i].second]) {
update(seg1, 1, 1, k, fs[i].second, 0);
ans += seg1[1];
ans += mod - seg2[1];
ans %= mod;
update(seg1, 1, 1, k, fs[i].second, cnt[fs[i].second]);
}
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
fish.cpp: In function 'int main()':
fish.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &f, &k, &mod);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &l, &x);
~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
484 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
484 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
536 KB |
Output is correct |
2 |
Incorrect |
2 ms |
536 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
536 KB |
Output is correct |
2 |
Incorrect |
230 ms |
4436 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
4436 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
4436 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
112 ms |
4436 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4436 KB |
Output is correct |
2 |
Incorrect |
7 ms |
4436 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
171 ms |
4436 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
256 ms |
4568 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
267 ms |
4568 KB |
Output is correct |
2 |
Incorrect |
340 ms |
4720 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
412 ms |
4720 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
429 ms |
5252 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
396 ms |
5376 KB |
Output is correct |
2 |
Correct |
826 ms |
7996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
749 ms |
10028 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
547 ms |
10032 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
901 ms |
11020 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |