Submission #53934

#	Time	Username	Problem	Language	Result	Execution time	Memory
53934		Diuven	Fish (IOI08_fish)	C++11	4 / 100	3070 ms	12012 KiB

fish

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=2e9;

struct fish {
    int len, col;
    bool operator < (const fish &a) const {
        return len<a.len;
    }
} F[MX];

int n,k,mod;

struct seg {
    static const int MX=1100000;
    int n, tree[MX];
    void init(int sz){
        n=sz;
        for(int i=1; i<MX; i++) tree[i]=1;
    }
    void upt(int v, int s, int e, int pos, int val){
        if(pos<s || e<pos) return;
        if(s==e){
            tree[v]+=val;
            return;
        }
        upt(v*2,s,(s+e)/2,pos,val);
        upt(v*2+1,(s+e)/2+1,e,pos,val);
        tree[v]=tree[v*2]*tree[v*2+1]%mod;
    }
    void upt(int pos, int val){
        upt(1,1,n,pos,val);
    }
    int prod(int v, int s, int e, int l, int r){
        if(r<s || e<l) return 1;
        if(l<=s && e<=r) return tree[v];
        return prod(v*2,s,(s+e)/2,l,r) * prod(v*2+1,(s+e)/2+1,e,l,r) % mod;
    }
    int prod(int l, int r){
        if(r<l) return 1;
        return prod(1,1,n,l,r);
    }
} Tree;

int solve(){
    int last[MX];
    fill(last+1, last+k+1, 0);
    for(int i=1; i<=n; i++){
        last[F[i].col]=i;
    }
    bool calc[MX]={};
    for(int i=1; i<=k; i++){
        int x=last[i];
        if(F[x].len*2<=F[n].len) continue;
        calc[x]=true;
    }
    int ans=0;
    int cnt[MX]={};
    Tree.init(k);
    for(int i=1, pos=0; i<=n; i++){
        if(!calc[i]) continue;
        int c=F[i].col;
        while(pos<n && F[pos+1].len*2<=F[i].len){
            pos++;
            cnt[F[pos].col]++;
            // Tree.upt(F[pos].col,1);
        }
        int now=1;
        for(int j=1; j<=k; j++){
            // cout<<j<<' '<<cnt[j]<<'\n';
            if(j==c){
                if(i==n) now=now*(cnt[j]+1)%mod;
                continue;
            }
            now=(now*(cnt[j]+1))%mod;
        }
        if(i==n) now=(now+mod-1)%mod;
        /*
        if(i==n) now=(Tree.prod(1,k)+mod-1)%mod;
        else now=Tree.prod(1,c-1) * Tree.prod(c+1, k) % mod;
        */
        // cout<<i<<' '<<F[i].len<<' '<<F[i].col<<": "<<now<<'\n';
        ans=(ans+now)%mod;
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k>>mod;
    for(int i=1; i<=n; i++)
        cin>>F[i].len>>F[i].col;
    sort(F+1, F+n+1);
    // for(int i=1; i<=n; i++) cout<<F[i].len<<' '<<F[i].col<<'\n';
    cout<<solve();
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 4 / 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