oj.uz

Submission #988714

# Submission time Handle Problem Language Result Execution time Memory
988714 2024-05-25T16:54:26 Z emad234 Fish (IOI08_fish) C++17
100 / 100
 772 ms 34340 KB 
#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const ll mxN = 5e5 + 5;
ll mod = 1e9 + 7;
using namespace std;
pii a[mxN];
ll compress[mxN];
ll seg[mxN * 4];
ll mn[mxN];
bool vis[mxN];
ll N,s,e;
ll combine(ll a,ll b) {return ((a * b) % mod);}
void update(ll ind,ll val){
    ind += N;
    seg[ind] += val;
    for(ind /= 2;ind;ind /= 2) seg[ind] = combine(seg[ind * 2],seg[ind * 2 + 1]);
}
ll query(ll l = 1,ll r = N,ll ind = 1){
    if(l > e || r < s) return 1;
    if(l >= s && r <= e) return seg[ind];
    ll md = (l + r)/ 2;
    return combine(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void prllseg(){
    ll ex = 1;
    for(ll i = 1;i < N * 2;i++){
        cout<<seg[i]<<' ';
        if(ex * 2 - 1 == i){
            cout<<'\n';
            ex *= 2;
        }
    }
}
signed main(){
    memset(compress,-1,sizeof compress);
    ll n,k;
    cin >>n>>k>>mod;
    N = exp2(ceil(log2(k)));
    for(ll i = 0;i < n;i++){
        cin >>a[i].F>>a[i].S;
    }
    sort(a,a + n,greater<>());
    ll id = 0;
    for(ll i = 0;i < N;i++) update(i,1);
    for(ll i = 0;i < n;i++){
        if(compress[a[i].S] == -1){
            compress[a[i].S] = id++;
        }a[i].S = compress[a[i].S];
        update(a[i].S,1);
    }
    id = 0;
    ll ans = 0;
    for(ll i = 0;i < n;i++){
        ll num = 1;
        if(vis[a[i].S]) continue;
        vis[a[i].S] = 1;
        while(a[id].F * 2 > a[i].F && id < n){
            update(a[id].S,-1);
            // cout<<a[id].S<<" TEST\n"; 
            mn[a[id].S] = i;
            id++;
        }
        // prllseg();
        if(i == 0){
            ans = seg[1];
            // cout<<a[i].F<<' '<<a[i].S<<'\n';
            // cout<<ans<<'\n';
            continue;
        }
        s = a[i].S + 2,e = N;
        num = combine(query(),num);
        s = a[i].S + 1, e = a[i].S + 1;
        // cout<<mn[a[i].S]<<' '<<a[i].S<<'\n';
        if(mn[a[i].S] == i){
            num = combine(query(),num);
        }else{
            num = combine(query() - 1,num);
            ans += num;
            num = 1;
            s = a[mn[a[i].S]].S + 1,e = a[i].S;
            num = combine(query(),num);
            s = a[i].S + 2,e = N;
            num = combine(num,query());
            // cout<<num<<'\n';
        }
        ans += num;
        ans %= mod;
        // cout<<a[i].F<<' '<<a[i].S<<'\n';
    }
    cout<<ans<<'\n';

}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 11348 KB Output is correct
2 Correct 145 ms 12784 KB Output is correct

Subtask #10
6.0 / 6.0

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

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 16532 KB Output is correct
2 Correct 324 ms 20140 KB Output is correct
3 Correct 333 ms 20396 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 19624 KB Output is correct
2 Correct 322 ms 20560 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 14672 KB Output is correct
2 Correct 318 ms 20776 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 19372 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 21532 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 19504 KB Output is correct
2 Correct 445 ms 24048 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 25264 KB Output is correct
2 Correct 357 ms 20384 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 23360 KB Output is correct
2 Correct 456 ms 24260 KB Output is correct
3 Correct 512 ms 25840 KB Output is correct
4 Correct 452 ms 24096 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 27196 KB Output is correct
2 Correct 772 ms 33324 KB Output is correct
3 Correct 751 ms 34340 KB Output is correct
4 Correct 769 ms 33344 KB Output is correct