oj.uz

Submission #898444

# Submission time Handle Problem Language Result Execution time Memory
898444 2024-01-04T16:36:32 Z abcvuitunggio Fish (IOI08_fish) C++17
9 / 100
 357 ms 40532 KB 
#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[f[i].second]=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;
        if (mx[t]!=i)
            continue;
        while (cur<=n&&f[cur].first*2<=l){
            update(1,1,k,order[f[cur].second]);
            cur++;
        }
        v[t].push_back(l);
        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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Incorrect 4 ms 21080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Incorrect 114 ms 29324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21080 KB Output is correct
2 Incorrect 6 ms 21080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 27296 KB Output is correct
2 Incorrect 154 ms 29588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 31064 KB Output is correct
2 Correct 162 ms 40532 KB Output is correct

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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