Submission #1005429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005429		gyg	Fish (IOI08_fish)	C++17	9 / 100	961 ms	30388 KiB

fish

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pii = pair<int, int>;
const int MAX_N = 5e5 + 5, MAX_K = 5e5 + 5;

int n, k;
lint m;
int len[MAX_N], a[MAX_N];

lint mod(lint x) { return (x + m) % m; }
lint st[4 * MAX_K];
void update(int i, lint x, int u = 1, int lo = 1, int hi = k) {
    if (i < lo || hi < i) return;
    if (lo == hi) { st[u] += x; return; }
    int mid = (lo + hi) / 2;
    update(i, x, 2 * u, lo, mid), update(i, x, 2 * u + 1, mid + 1, hi);
    st[u] = mod(st[2 * u] * st[2 * u + 1]);
}
lint query(int l, int r, int u = 1, int lo = 1, int hi = k) {
    if (l > r) return 1; // 0?
    if (r < lo || hi < l) return 1;
    if (l <= lo && hi <= r) return st[u];
    int mid = (lo + hi) / 2;
    return mod(query(l, r, 2 * u, lo, mid) * query(l, r, 2 * u + 1, mid + 1, hi));
}

void precomp() {
    vector<pii> ord;
    for (int i = 1; i <= n; i++) ord.push_back({len[i], a[i]});
    sort(ord.rbegin(), ord.rend());

    unordered_map<int, int> val;
    for (pii x : ord) {        
        if (val.count(x.second)) continue;
        val.insert({x.second, val.size() + 1});
    }   
    
    for (int i = 1; i <= n; i++) {
        len[i] = ord[i - 1].first, a[i] = val[ord[i - 1].second];
        update(a[i], 1);
    }
    for (int i = 1; i <= k; i++) update(i, 1);


    // for (int i = 1; i <= n; i++) {
    //     cout << len[i] << " " << a[i] << endl;
    // }
    // cout << endl;
    // cout << query(1, 2) << endl;
}

lint comp() {
    lint ans = 0;
    unordered_map<int, int> max_freq;
    int max_seen = 0;
    int r = 1;
    for (int l = 1; l <= n; l++) {
        while (r != n + 1 && 2 * len[r] > len[l]) 
            update(a[r], -1), r++;
        update(a[l], 1);
        
        lint new_ans = 0;
        if (l == 1) {
            assert(a[l] == 1);
            new_ans = mod(query(2, k) * mod(query(1, 1) - 1));
            max_seen = 1; 
            for (int i = 1; i <= k; i++) max_freq[i] = query(i, i);
        } else {
            bool cond1 = false, cond2 = false;
            if (a[l] > max_seen)
                cond1 = true, max_seen = a[l];
            if (query(a[l], a[l]) > max_freq[a[l]])
                cond2 = true, max_freq[a[l]] = query(a[l], a[l]);
            if (cond2)
                new_ans = mod(query(1, a[l] - 1) * query(a[l] + 1, k));
            if (cond1) {
                lint x = (cond2) ? mod(query(a[l], a[l]) - 2) : mod(query(a[l], a[l]) - 1); 
                new_ans = mod(new_ans + mod(query(a[l] + 1, k) * x));
            }
        }

        // cout << l << ": " << new_ans << endl;
        
        update(a[l], -1);
        ans = mod(ans + new_ans);
    }
    return ans;
}

int main() {
    // freopen("fish.in", "r", stdin), freopen("fish.out", "w", stdout);
    cin >> n >> k >> m;
    for (int i = 1; i <= n; i++) cin >> len[i] >> a[i];

    precomp();
    lint ans = comp();
    cout << ans << '\n';
} 

• Subtask 1: 4 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 5 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5