oj.uz

Submission #53891

# Submission time Handle Problem Language Result Execution time Memory
53891 2018-07-01T14:56:26 Z Diuven Fish (IOI08_fish) C++11
4 / 100
 293 ms 9840 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 {
    int n, tree[25010*4];
    void init(int sz){
        n=sz;
        for(int i=1; i<4*n; 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[25010];
    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[last[i]]=true;
    }
    int ans=0;
    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++;
            Tree.upt(F[pos].col,1);
        }
        int now=0;
        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);
    cout<<solve();
    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1000 KB Output is correct

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 177 ms 9024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 157 ms 9088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 173 ms 9840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -