Submission #898454

#	Time	Username	Problem	Language	Result	Execution time	Memory
898454		abcvuitunggio	Fish (IOI08_fish)	C++17	100 / 100	569 ms	55380 KiB

fish

#include <bits/stdc++.h>
using namespace std;
int n,k,m,res,mx[500001],L[500001],mn[500001],order[500001],st[2000001];
pair <int, int> f[500001];
vector <int> v[500001];
void update(int node, int l, int r, int i){
    if (l>i||r<i)
        return;
    if (l==r){
        st[node]=(st[node]+1)%m;
        return;
    }
    int mid=(l+r)>>1;
    update(node<<1,l,mid,i);
    update(node<<1|1,mid+1,r,i);
    st[node]=st[node<<1]*st[node<<1|1]%m;
}
int get(int node, int l, int r, int u, int v){
    if (l>v||r<u||u>v)
        return 1;
    if (l>=u&&r<=v)
        return st[node];
    int mid=(l+r)>>1;
    return get(node<<1,l,mid,u,v)*get(node<<1|1,mid+1,r,u,v)%m;
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> k >> m;
    fill(mn,mn+k+1,1000000001);
    for (int i=1;i<=n;i++){
        cin >> f[i].first >> f[i].second;
        mn[f[i].second]=min(mn[f[i].second],f[i].first);
    }
    sort(f+1,f+n+1);
    fill(st,st+n*4+1,1);
    int tmp=k;
    for (int i=n;i;i--){
        if (mx[f[i].second])
            continue;
        mx[f[i].second]=i;
        L[tmp]=f[i].first;
        order[f[i].second]=tmp;
        tmp--;
    }
    int cur=1;
    for (int i=1;i<=n;i++){
        int l=f[i].first,t=f[i].second;
        v[t].push_back(l);
        if (mx[t]!=i)
            continue;
        while (cur<=n&&f[cur].first*2<=l){
            update(1,1,k,order[f[cur].second]);
            cur++;
        }
        int j=lower_bound(L+1,L+k+1,mn[t]*2)-L;
        j=max(j,order[t]+1);
        int x=get(1,1,k,1,order[t]-1)*get(1,1,k,order[t]+1,j-1)%m;
        res=(res+x*get(1,1,k,order[t],order[t]))%m;
        int val=v[t][upper_bound(v[t].begin(),v[t].end(),l/2)-v[t].begin()];
        int j2=lower_bound(L+1,L+k+1,val*2)-L-1;
        res=(res+x*(get(1,1,k,j,j2)+m-1))%m;
    }
    cout << res;
}

• 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