oj.uz

Submission #898454

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

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 124 ms 31828 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 28812 KB Output is correct
2 Correct 71 ms 28744 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21080 KB Output is correct
2 Correct 6 ms 21084 KB Output is correct
3 Correct 6 ms 21240 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 29324 KB Output is correct
2 Correct 171 ms 31728 KB Output is correct
3 Correct 148 ms 32012 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 32008 KB Output is correct
2 Correct 154 ms 39424 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 29268 KB Output is correct
2 Correct 171 ms 32152 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 32084 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 32652 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 31884 KB Output is correct
2 Correct 182 ms 34452 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 34956 KB Output is correct
2 Correct 244 ms 37256 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 35956 KB Output is correct
2 Correct 298 ms 42220 KB Output is correct
3 Correct 341 ms 44028 KB Output is correct
4 Correct 296 ms 42132 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 36436 KB Output is correct
2 Correct 552 ms 54608 KB Output is correct
3 Correct 484 ms 55380 KB Output is correct
4 Correct 569 ms 51540 KB Output is correct