oj.uz

Submission #1005280

# Submission time Handle Problem Language Result Execution time Memory
1005280 2024-06-22T09:42:05 Z bachhoangxuan Fish (IOI08_fish) C++17
100 / 100
 457 ms 51484 KB 
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int maxn = 5e5+5;

int n,k,mod,mx[maxn];
vector<int> p[maxn];
int c[maxn],tree[4*maxn];

void build(int l,int r,int id){
    if(l==r){
        tree[id]=(c[l]+1)%mod;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    tree[id]=tree[id<<1]*tree[id<<1|1]%mod;
}
void update(int l,int r,int id,int x){
    if(l==r){
        tree[id]=(c[l]+1)%mod;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) update(l,mid,id<<1,x);
    else update(mid+1,r,id<<1|1,x);
    tree[id]=tree[id<<1]*tree[id<<1|1]%mod;
}
int query(int l,int r,int id,int tl,int tr){
    if(tr<l || r<tl) return 1;
    if(tl<=l && r<=tr) return tree[id];
    int mid=(l+r)>>1;
    return query(l,mid,id<<1,tl,tr)*query(mid+1,r,id<<1|1,tl,tr)%mod;
}

signed main(){
    //freopen("FISH.INP","r",stdin);
    //freopen("FISH.OUT","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> k >> mod;
    vector<pii> d;
    for(int i=1;i<=n;i++){
        int l,x;cin >> l >> x;
        mx[x]=max(mx[x],l);
        d.push_back({l,x});
    }
    vector<int> ord(k);
    iota(ord.begin(),ord.end(),1);
    sort(ord.begin(),ord.end(),[&](int x,int y){
        return mx[x]>mx[y];
    });
    for(int i=0;i<k;i++) mx[ord[i]]=i+1;
    for(auto &[l,x]:d) x=mx[x],p[x].push_back(l);
    for(int i=1;i<=k;i++){
        c[i]=(int)p[i].size();
        sort(p[i].begin(),p[i].end());
    }
    sort(d.begin(),d.end());
    build(1,k,1);

    int pos=1,total=0;
    for(int i=1;i<=k;i++){
        while(!d.empty() && d.back().fi>p[i].back()/2){
            int x=d.back().se;d.pop_back();
            c[x]--;update(1,k,1,x);
        }
        int l=1,r=i-1,pos=i;
        while(l<=r){
            int mid=(l+r)>>1;
            if(p[mid].back()/2>=p[i][c[i]]) l=mid+1;
            else pos=mid,r=mid-1;
        }
        int rt=(i==k?1:query(1,k,1,i+1,k));
        int lt=(pos<i?query(1,k,1,pos,i-1)-1:0);
        lt=(lt+c[i]+1)%mod;
        total=(total+lt*rt)%mod;
    }
    cout << total << '\n';
}

Compilation message

fish.cpp: In function 'int main()':
fish.cpp:64:9: warning: unused variable 'pos' [-Wunused-variable]
   64 |     int pos=1,total=0;
      |         ^~~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 133 ms 26576 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 21196 KB Output is correct
2 Correct 72 ms 23756 KB Output is correct

Subtask #10
6.0 / 6.0

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

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 24416 KB Output is correct
2 Correct 156 ms 29888 KB Output is correct
3 Correct 146 ms 30804 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 27328 KB Output is correct
2 Correct 145 ms 27584 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 24260 KB Output is correct
2 Correct 142 ms 27836 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 26556 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 30144 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 28348 KB Output is correct
2 Correct 226 ms 32192 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 32044 KB Output is correct
2 Correct 209 ms 32000 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 32188 KB Output is correct
2 Correct 268 ms 32348 KB Output is correct
3 Correct 322 ms 38076 KB Output is correct
4 Correct 257 ms 35808 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 34408 KB Output is correct
2 Correct 451 ms 50624 KB Output is correct
3 Correct 457 ms 51484 KB Output is correct
4 Correct 436 ms 47552 KB Output is correct