Submission #234175

#	Time	Username	Problem	Language	Result	Execution time	Memory
234175		Leonardo_Paes	Fish (IOI08_fish)	C++17	0 / 100	340 ms	24808 KiB

fish

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

#define f first
#define s second

const int maxn = 5e5+10;

int f, k, m, last[maxn];

ll tree[4*maxn];

pii vet[maxn];

void build(int node, int l, int r){
    if(l == r){
        tree[node] = 1;
        return;
    }

    int mid = (l + r) >> 1;

    build(2*node, l, mid), build(2*node+1, mid+1, r);

    tree[node] = (tree[2*node] * tree[2*node+1])%m;
}

void update(int node, int l, int r, int idx, int v){
    if(l == r){
        tree[node] += v;
        return;
    }

    int mid = (l + r) >> 1;

    if(idx <= mid) update(2*node, l, mid, idx, v);
    else update(2*node+1, mid+1, r, idx, v);

    tree[node] = (tree[2*node] * tree[2*node+1])%m;
}

ll query(int node, int tl, int tr, int l, int r){
    if(tl > r or tr < l) return 1LL;
    if(tl >= l and tr <= r) return tree[node];

    int mid = (tl + tr) >> 1;

    return (query(2*node, tl, mid, l, r)*query(2*node+1, mid+1, tr, l, r))%m;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin >> f >> k >> m;

    for(int i=1; i<=f; i++){
        cin >> vet[i].f >> vet[i].s;
        last[vet[i].s] = i;
    }

    sort(vet+1, vet+f+1);

    build(1, 1, f);

    ll ans = 0LL;

    for(int i=1, j=1; i<=f and j<=f; i++){
        if(last[vet[i].s] == i){
            update(1, 1, f, vet[j].s, 1);
            ans += query(1, 1, f, 1, f);
            update(1, 1, f, vet[j].s, -1);
        }
        while(vet[j].f + vet[j].f <= vet[i].f){
            update(1, 1, f, vet[j].s, 1);
            j++;
        }
    }

    cout << (ans+m)%m << endl;

    return 0;
}

• Subtask 1: 0 / 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: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5