oj.uz

Submission #53934

# Submission time Handle Problem Language Result Execution time Memory
53934 2018-07-02T01:18:56 Z Diuven Fish (IOI08_fish) C++11
4 / 100
 3000 ms 12012 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7160 KB Output isn't correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7272 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7328 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7328 KB Output isn't correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 7328 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7328 KB Output isn't correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 8836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 8836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 11220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 11220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1787 ms 11220 KB Output isn't correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 11332 KB Time limit exceeded

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3055 ms 11332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3062 ms 11432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 11500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 12012 KB Time limit exceeded
2 Halted 0 ms 0 KB -