Submission #998966

#	Time	Username	Problem	Language	Result	Execution time	Memory
998966		phoebe	Fish (IOI08_fish)	C++17	100 / 100	811 ms	65536 KiB

fish

#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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5