oj.uz

답안 #53794

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53794 2018-07-01T08:01:19 Z 강태규(#1435) Fish (IOI08_fish) C++11
9 / 100
 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);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

# 결과 실행 시간 메모리 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 -

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 396 ms 5376 KB Output is correct
2 Correct 826 ms 7996 KB Output is correct

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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