oj.uz

Submission #998966

# Submission time Handle Problem Language Result Execution time Memory
998966 2024-06-15T02:36:50 Z phoebe Fish (IOI08_fish) C++17
100 / 100
 811 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("03")
 
#define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;
 
const int maxn = 5e5 + 10;
int f, k, m, largest_fish[maxn] = {0}, idx[maxn], 
cnt[maxn] = {0}, tree[maxn * 3], all[maxn], target[maxn], 
second_largest[maxn] = {0};
vector<pii> order;
 
void update(int x, int v, int tl = 0, int tr = maxn, int i = 1){
    if (x < tl || x > tr) return;
    if (tl == tr){
        tree[i] = v; return;
    }
    int tm = (tl + tr) / 2;
    update(x, v, tl, tm, i * 2); update(x, v, tm + 1, tr, i * 2 + 1);
    tree[i] = (tree[i * 2] * tree[i * 2 + 1]) % m;
}
 
int range(int l, int r, int tl = 0, int tr = maxn, int i = 1){
    if (l > tr || tl > r) return 1;
    if (l <= tl && tr <= r) return tree[i];
    int tm = (tl + tr) / 2;
    return (range(l, r, tl, tm, i * 2) * 
    range(l, r, tm + 1, tr, i * 2 + 1)) % m;
}
 
signed main(){
    // freopen("fish.in", "r", stdin);
    // freopen("fish.out", "w", stdout);
    fill(tree, tree + maxn * 3, 1);
    fill(all, all + maxn, -1);
    fill(second_largest, second_largest + maxn, INF);
    cin >> f >> k >> m;
    FOR(i, f){
        int length, gem; cin >> length >> gem; gem--;
        largest_fish[gem] = max(largest_fish[gem], length);
        order.PB({length, gem});
        cnt[gem]++;
    }
    FOR(i, k) target[i] = largest_fish[i] / 2; // <=
    FOR(i, f){
        if (order[i].F <= target[order[i].S]) continue;
        second_largest[order[i].S] = min(second_largest[order[i].S], 
        order[i].F);
    }
    pii bruh[k];
    FOR(i, k) bruh[i] = {second_largest[i] * 2, i};
    sort(bruh, bruh + k);
    // return 0;
    pii mx[k];
    FOR(i, k) mx[i] = {largest_fish[i], i};
    sort(mx, mx + k);
    FOR(i, k){
        idx[mx[i].S] = i;
        update(i, cnt[mx[i].S] + 1);
    }
    // return 0;
    int r = k - 1;
    for (int l = k - 1; l >= 0; l--){
        while (r >= 0 && mx[r].F >= bruh[l].F) r--;
        all[bruh[l].S] = r;
    }
    sort(ALL(order));
    int l = f - 1, re = 0;
    for (int r = k - 1; r >= 0; r--){
        int gem = mx[r].S;
        while (l >= 0 && order[l].F * 2 > largest_fish[gem]){
            cnt[order[l].S]--; 
            update(idx[order[l].S], cnt[order[l].S] + 1);
            l--;
        }
        if (all[gem] == -1) all[gem] = r;
        update(idx[gem], cnt[gem]); 
        re += range(0, r); re %= m;
        update(idx[gem], 1); 
        re += range(0, all[gem]); re %= m;
        update(idx[gem], cnt[gem] + 1);
    }
    cout << re << endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 3 ms 25276 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25180 KB Output is correct
2 Correct 265 ms 39088 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25180 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25408 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 30896 KB Output is correct
2 Correct 132 ms 32180 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 25436 KB Output is correct
2 Correct 7 ms 25436 KB Output is correct
3 Correct 7 ms 25472 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 35868 KB Output is correct
2 Correct 286 ms 39856 KB Output is correct
3 Correct 270 ms 39924 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 39344 KB Output is correct
2 Correct 274 ms 40112 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 37208 KB Output is correct
2 Correct 287 ms 40368 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 39856 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 41136 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 42928 KB Output is correct
2 Correct 428 ms 46728 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 47280 KB Output is correct
2 Correct 350 ms 42416 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 45340 KB Output is correct
2 Correct 447 ms 46928 KB Output is correct
3 Correct 490 ms 53936 KB Output is correct
4 Correct 432 ms 46628 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 55096 KB Output is correct
2 Correct 723 ms 65536 KB Output is correct
3 Correct 811 ms 65536 KB Output is correct
4 Correct 736 ms 63000 KB Output is correct