oj.uz

답안 #53790

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53790 2018-07-01T07:45:29 Z 강태규(#1435) Fish (IOI08_fish) C++11
0 / 100
 901 ms 18088 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;
    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;
        }
        if (i == 0) {
            for (int it = 1; it <= k; ++it) mx[it] = cnt[it];
            ans = seg1[1];
        }
        else {
            if (cnt[fs[i].second] == mx[fs[i].second]) {
                update(seg1, 1, 1, k, fs[i].second, 0);
                ans += seg1[1];
                ans %= mod;
                update(seg1, 1, 1, k, fs[i].second, cnt[fs[i].second]);
            }
            ans += seg2[1];
            ans %= mod;
        }
        update(seg2, 1, 1, k, fs[i].second, 0);
        ch[fs[i].second] = 1;
    }
    
    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);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 376 KB Output isn't correct

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 412 KB Output isn't correct

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 412 KB Output isn't correct

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 460 KB Output is correct
2 Incorrect 2 ms 460 KB Output isn't correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 680 KB Output is correct
2 Incorrect 292 ms 4436 KB Output isn't correct

Subtask #7
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4436 KB Output isn't correct

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4436 KB Output isn't correct

Subtask #9
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 136 ms 4436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4436 KB Output is correct
2 Correct 6 ms 4436 KB Output is correct
3 Incorrect 7 ms 4436 KB Output isn't correct

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 197 ms 4436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 286 ms 4516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 4516 KB Output is correct
2 Incorrect 340 ms 11804 KB Output isn't correct

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 329 ms 11804 KB Output isn't correct

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 417 ms 12336 KB Output isn't correct

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 396 ms 12416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 741 ms 17020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 598 ms 17132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 901 ms 18088 KB Output isn't correct
2 Halted 0 ms 0 KB -