Submission #1314933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314933		exoworldgd	Fish (IOI08_fish)	C++20	100 / 100	489 ms	36032 KiB

fish

#pragma GCC optimize("O5,unroll-loops,inline,fast-math")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
#define exoworldgd cin.tie(0)->sync_with_stdio(0), cout.tie(0)
using namespace std;
const int K=1<<20,N=5e5+5;
int n,k,mod,a[N],b[N],ord[N],last[N],nxt[N],cnt,ans,ok[N];
pair<int,int> p[N];
struct segTree{
    int t[K];
    void build(int l,int r,int i){
        t[i]=1;
        if(l==r)return;
        int m=(l+r)/2;
        build(l,m,i*2), build(m+1,r,i*2+1);
    }
    void build(){build(1,k,1);}
    void update(int l,int r,int i,int x,int v){
        if(x<l||r<x)return;
        if(l==r)return void(t[i]=(t[i]+v)%mod);
        int m=(l+r)/2;
        update(l,m,i*2,x,v), update(m+1,r,i*2+1,x,v), t[i]=t[i*2]*t[i*2+1]%mod;
    }
    void update(int x,int v){update(1,k,1,x,v);}
    int query(int l,int r,int i,int x,int y){
        if(y<l||r<x)return 1;
        if(x<=l&&r<=y)return t[i];
        int m=(l+r)/2;
        return query(l,m,i*2,x,y)*query(m+1,r,i*2+1,x,y)%mod;
    }
    int query(int x,int y){return query(1,k,1,x,y);}
}seg;
signed main(void) {
    exoworldgd;
    cin >> n >> k >> mod;
    for(int i=1;i<=n;i++)cin >> p[i].first >> p[i].second;
    sort(p+1,p+n+1);
    cnt=k;
    for(int i=n;i>=1;i--){
        auto [l,t]=p[i];
        if(!ord[t]) b[cnt]=l, ord[t]=cnt, last[t]=l, ok[i]=1, cnt--;
        nxt[i]=last[t], last[t]=l;
    }
    seg.build();
    for(int i=1,j=1,x;i<=n;i++)if(ok[i]){
        auto [l,t]=p[i];
        while(j<=n&&l>=p[j].first*2)x=p[j].second, seg.update(ord[x],1), last[x]=nxt[j], j++;
        ans+=seg.query(1,ord[t]), ans+=mod+seg.query(1,ord[t]-1)*(seg.query(ord[t]+1,lower_bound(b+1,b+k+1,last[t]*2)-b-1)-1), ans%=mod;
    }
    cout << ans;
}

• 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