oj.uz

Submission #53806

# Submission time Handle Problem Language Result Execution time Memory
53806 2018-07-01T08:35:47 Z 강태규(#1435) Fish (IOI08_fish) C++11
9 / 100
 1030 ms 11060 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;
        }
        if (i)
            update(seg2, 1, 1, k, fs[i].second, min(cnt[fs[i].second], mx[fs[i].second] - 1));
        ans += seg2[1];
        //printf("From %d %d\n", fs[i].second, seg2[i]);
        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;
                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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 432 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Output isn't correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Incorrect 3 ms 672 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct
2 Incorrect 207 ms 4492 KB Output isn't correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4492 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4492 KB Output isn't correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 4492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4492 KB Output is correct
2 Incorrect 7 ms 4492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 192 ms 4492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 4616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 4616 KB Output is correct
2 Incorrect 327 ms 4904 KB Output isn't correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 4904 KB Output isn't correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 472 ms 5428 KB Output isn't correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 5428 KB Output is correct
2 Correct 883 ms 7896 KB Output is correct

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 915 ms 10136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 646 ms 10136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1030 ms 11060 KB Output isn't correct
2 Halted 0 ms 0 KB -