oj.uz

Submission #696867

# Submission time Handle Problem Language Result Execution time Memory
696867 2023-02-07T13:28:20 Z puppy Fish (IOI08_fish) C++17
0 / 100
 341 ms 44864 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int F, K, M;
pair<int, int> fish[500005]; //(length, color)
struct mulseg
{
    vector<int> tree;
    mulseg(int n)
    {
        int sz = 1 << ((int)ceil(log2(n+1))+1);
        tree.resize(sz);
    }
    int init(int s, int e, int node, vector<int> &arr)
    {
        if (s == e) return tree[node] = arr[s] % M;
        return tree[node] = init(s, (s+e)/2, 2*node, arr) * init((s+e)/2+1, e, 2*node+1, arr) % M;
    }
    void upd(int s, int e, int node, int id, int diff)
    {
        if (e < id || id < s) return;
        if (s == e) {
            tree[node] = (tree[node] + diff + M) % M;
            return;
        }
        upd(s, (s+e)/2, 2*node, id, diff);
        upd((s+e)/2+1, e, 2*node+1, id, diff);
        tree[node] = tree[2*node] * tree[2*node+1] % M;
    }
    int query(int s, int e, int node, int l, int r)
    {
        if (l > r) return 1;
        if (e < l || r < s) return 1;
        if (l <= s && e <= r) return tree[node];
        return query(s, (s+e)/2, 2*node, l, r) * query((s+e)/2+1, e, 2*node+1, l, r) % M;
    }
};
vector<int> lst[500005];
pair<int, int> x[500005];
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> F >> K >> M;
    for (int i = 0; i < F; i++) {
        cin >> fish[i].first >> fish[i].second;
    }
    sort(fish, fish + F);
    vector<int> trans(1, 0);
    vector<bool> vis(K+1);
    for (int i = F - 1; i >= 0; i--) {
        if (!vis[fish[i].second]) {
            trans.push_back(fish[i].second);
            vis[fish[i].second] = true;
        }
    }
    fill(x, x + 500005, make_pair(-1, -1));
    vector<int> to(K+1);
    for (int i = 1; i <= K; i++) to[trans[i]] = i;
    for (int i = 0; i < F; i++) fish[i].second = to[fish[i].second];
    for (int i = F-1; i >= 0; i--) {
        if (x[fish[i].second].second == -1) {
            x[fish[i].second] = make_pair(fish[i].first, i);
        }
    }
    for (int i = 0; i < F; i++) lst[fish[i].second].push_back(fish[i].first);
    mulseg seg(K);
    vector<int> cnt(K+1);
    int fin = fish[F-1].first;
    int pos = 0;
    while (pos < F && fish[pos].first <= fin/2) pos++;
    for (int i = 0; i < pos; i++) cnt[fish[i].second]++;
    for (int i = 1; i <= K; i++) cnt[i]++;
    seg.init(1, K, 1, cnt);
    int ans = 0;
    for (int i = 1; i <= K; i++) {
        int now = x[i].second;
        while (pos > 0 && fish[pos-1].first > fish[now].first/2) {
            seg.upd(1, K, 1, fish[pos-1].second, -1);
            pos--;
        }
        int len = 2 * *upper_bound(lst[i].begin(), lst[i].end(), fish[now].first/2);
        //길이가 len보다 작은 최소의 p를 찾자
        int l = 1, r = K;
        while (l < r) {
            int m = l + r >> 1;
            if (x[m].first >= len) l = m+1;
            else r = m;
        }
        ans += (seg.query(1, K, 1, l, K));
        ans %= M;
    }
    assert(0 <= ans && ans < M);
    cout << ans << '\n';
}

Compilation message

fish.cpp: In function 'int main()':
fish.cpp:85:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |             int m = l + r >> 1;
      |                     ~~^~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19896 KB Output is correct
2 Incorrect 137 ms 32076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 28480 KB Output is correct
2 Incorrect 161 ms 33268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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