oj.uz

Submission #904271

# Submission time Handle Problem Language Result Execution time Memory
904271 2024-01-12T02:10:22 Z bachhoangxuan Railway Trip 2 (JOI22_ho_t4) C++17
100 / 100
 721 ms 165764 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/

#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=100005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=20;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=131;

struct ST{
    int L[4*maxn],R[4*maxn],nL[maxn],nR[maxn];
    void build(int l,int r,int id){
        if(l==r){
            L[id]=nL[l];
            R[id]=nR[r];
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,id<<1);build(mid+1,r,id<<1|1);
        L[id]=min(L[id<<1],L[id<<1|1]);
        R[id]=max(R[id<<1],R[id<<1|1]);
    }
    pii query(int l,int r,int id,int tl,int tr){
        if(tr<l || r<tl) return {inf,-inf};
        if(tl<=l && r<=tr) return {L[id],R[id]};
        int mid=(l+r)>>1;
        pii pl=query(l,mid,id<<1,tl,tr);
        pii pr=query(mid+1,r,id<<1|1,tl,tr);
        return {min(pl.fi,pr.fi),max(pl.se,pr.se)};
    }
}S[maxl];

int n,k,m;
vector<pii> pL[maxn],pR[maxn];

void solve(){
    cin >> n >> k >> m;
    for(int i=1;i<=m;i++){
        int l,r;cin >> l >> r;
        if(l<=r){
            int nl=min(r,l+k);
            pR[l].push_back({r,i});
            pR[nl].push_back({r,-i});
        }
        else{
            swap(l,r);
            int nr=max(l,r-k);
            pL[r].push_back({l,i});
            pL[nr].push_back({l,-i});
        }
    }
    set<pii> s;
    for(int i=1;i<=n;i++){
        for(auto x:pR[i]){
            if(x.se>0) s.insert(x);
            else s.erase({x.fi,-x.se});
        }
        S[0].nR[i]=i;
        if(!s.empty()) S[0].nR[i]=s.rbegin()->fi;
        //cout << S[0].nR[i] << ' ';
    }
    //cout << '\n';
    s.clear();
    for(int i=n;i>=1;i--){
        for(auto x:pL[i]){
            if(x.se>0) s.insert(x);
            else s.erase({x.fi,-x.se});
        }
        S[0].nL[i]=i;
        if(!s.empty()) S[0].nL[i]=s.begin()->fi;
        //cout << S[0].nL[i] << ' ';
    }
    //cout << '\n';
    S[0].build(1,n,1);
    for(int j=1;j<18;j++){
        for(int i=1;i<=n;i++){
            int l=S[j-1].nL[i],r=S[j-1].nR[i];
            tie(S[j].nL[i],S[j].nR[i])=S[j-1].query(1,n,1,l,r);
        }
        S[j].build(1,n,1);
    }
    int q;cin >> q;
    for(int i=1;i<=q;i++){
        int l,r,t,cnt=1;
        cin >> l >> t;r=l;
        for(int j=17;j>=0;j--){
            auto [nl,nr] = S[j].query(1,n,1,l,r);
            if(t<nl || nr<t) cnt+=(1<<j),l=nl,r=nr;
        }
        if(cnt==(1<<18)) cout << -1 << '\n';
        else cout << cnt << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 109220 KB Output is correct
2 Correct 25 ms 109244 KB Output is correct
3 Correct 17 ms 109148 KB Output is correct
4 Correct 17 ms 109656 KB Output is correct
5 Correct 17 ms 109336 KB Output is correct
6 Correct 17 ms 109404 KB Output is correct
7 Correct 18 ms 109140 KB Output is correct
8 Correct 16 ms 109148 KB Output is correct
9 Correct 18 ms 109404 KB Output is correct
10 Correct 17 ms 107100 KB Output is correct
11 Correct 17 ms 109148 KB Output is correct
12 Correct 18 ms 109148 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 109220 KB Output is correct
2 Correct 25 ms 109244 KB Output is correct
3 Correct 17 ms 109148 KB Output is correct
4 Correct 17 ms 109656 KB Output is correct
5 Correct 17 ms 109336 KB Output is correct
6 Correct 17 ms 109404 KB Output is correct
7 Correct 18 ms 109140 KB Output is correct
8 Correct 16 ms 109148 KB Output is correct
9 Correct 18 ms 109404 KB Output is correct
10 Correct 17 ms 107100 KB Output is correct
11 Correct 17 ms 109148 KB Output is correct
12 Correct 18 ms 109148 KB Output is correct
13 Correct 24 ms 111444 KB Output is correct
14 Correct 24 ms 111444 KB Output is correct
15 Correct 21 ms 111452 KB Output is correct
16 Correct 21 ms 111452 KB Output is correct
17 Correct 30 ms 111704 KB Output is correct
18 Correct 24 ms 111444 KB Output is correct
19 Correct 23 ms 111452 KB Output is correct
20 Correct 20 ms 111452 KB Output is correct
21 Correct 18 ms 111452 KB Output is correct
22 Correct 23 ms 111444 KB Output is correct
23 Correct 23 ms 111452 KB Output is correct
24 Correct 24 ms 111452 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 151628 KB Output is correct
2 Correct 287 ms 151380 KB Output is correct
3 Correct 333 ms 152248 KB Output is correct
4 Correct 274 ms 151120 KB Output is correct
5 Correct 193 ms 160852 KB Output is correct
6 Correct 328 ms 158804 KB Output is correct
7 Correct 163 ms 163888 KB Output is correct
8 Correct 129 ms 154420 KB Output is correct
9 Correct 109 ms 154196 KB Output is correct
10 Correct 310 ms 158848 KB Output is correct
11 Correct 301 ms 158944 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 154452 KB Output is correct
2 Correct 402 ms 161216 KB Output is correct
3 Correct 521 ms 153684 KB Output is correct
4 Correct 317 ms 164800 KB Output is correct
5 Correct 280 ms 162484 KB Output is correct
6 Correct 283 ms 162644 KB Output is correct
7 Correct 520 ms 160156 KB Output is correct
8 Correct 440 ms 159604 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 162352 KB Output is correct
2 Correct 699 ms 153480 KB Output is correct
3 Correct 647 ms 150288 KB Output is correct
4 Correct 559 ms 148564 KB Output is correct
5 Correct 432 ms 147384 KB Output is correct
6 Correct 401 ms 147044 KB Output is correct
7 Correct 340 ms 159568 KB Output is correct
8 Correct 18 ms 109148 KB Output is correct
9 Correct 23 ms 111452 KB Output is correct
10 Correct 358 ms 162900 KB Output is correct
11 Correct 426 ms 165764 KB Output is correct
12 Correct 418 ms 162928 KB Output is correct
13 Correct 432 ms 165164 KB Output is correct
14 Correct 18 ms 109148 KB Output is correct
15 Correct 24 ms 111452 KB Output is correct
16 Correct 326 ms 159060 KB Output is correct
17 Correct 609 ms 159604 KB Output is correct
18 Correct 598 ms 159712 KB Output is correct
19 Correct 545 ms 159564 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 109220 KB Output is correct
2 Correct 25 ms 109244 KB Output is correct
3 Correct 17 ms 109148 KB Output is correct
4 Correct 17 ms 109656 KB Output is correct
5 Correct 17 ms 109336 KB Output is correct
6 Correct 17 ms 109404 KB Output is correct
7 Correct 18 ms 109140 KB Output is correct
8 Correct 16 ms 109148 KB Output is correct
9 Correct 18 ms 109404 KB Output is correct
10 Correct 17 ms 107100 KB Output is correct
11 Correct 17 ms 109148 KB Output is correct
12 Correct 18 ms 109148 KB Output is correct
13 Correct 24 ms 111444 KB Output is correct
14 Correct 24 ms 111444 KB Output is correct
15 Correct 21 ms 111452 KB Output is correct
16 Correct 21 ms 111452 KB Output is correct
17 Correct 30 ms 111704 KB Output is correct
18 Correct 24 ms 111444 KB Output is correct
19 Correct 23 ms 111452 KB Output is correct
20 Correct 20 ms 111452 KB Output is correct
21 Correct 18 ms 111452 KB Output is correct
22 Correct 23 ms 111444 KB Output is correct
23 Correct 23 ms 111452 KB Output is correct
24 Correct 24 ms 111452 KB Output is correct
25 Correct 410 ms 151628 KB Output is correct
26 Correct 287 ms 151380 KB Output is correct
27 Correct 333 ms 152248 KB Output is correct
28 Correct 274 ms 151120 KB Output is correct
29 Correct 193 ms 160852 KB Output is correct
30 Correct 328 ms 158804 KB Output is correct
31 Correct 163 ms 163888 KB Output is correct
32 Correct 129 ms 154420 KB Output is correct
33 Correct 109 ms 154196 KB Output is correct
34 Correct 310 ms 158848 KB Output is correct
35 Correct 301 ms 158944 KB Output is correct
36 Correct 452 ms 154452 KB Output is correct
37 Correct 402 ms 161216 KB Output is correct
38 Correct 521 ms 153684 KB Output is correct
39 Correct 317 ms 164800 KB Output is correct
40 Correct 280 ms 162484 KB Output is correct
41 Correct 283 ms 162644 KB Output is correct
42 Correct 520 ms 160156 KB Output is correct
43 Correct 440 ms 159604 KB Output is correct
44 Correct 615 ms 162352 KB Output is correct
45 Correct 699 ms 153480 KB Output is correct
46 Correct 647 ms 150288 KB Output is correct
47 Correct 559 ms 148564 KB Output is correct
48 Correct 432 ms 147384 KB Output is correct
49 Correct 401 ms 147044 KB Output is correct
50 Correct 340 ms 159568 KB Output is correct
51 Correct 18 ms 109148 KB Output is correct
52 Correct 23 ms 111452 KB Output is correct
53 Correct 358 ms 162900 KB Output is correct
54 Correct 426 ms 165764 KB Output is correct
55 Correct 418 ms 162928 KB Output is correct
56 Correct 432 ms 165164 KB Output is correct
57 Correct 18 ms 109148 KB Output is correct
58 Correct 24 ms 111452 KB Output is correct
59 Correct 326 ms 159060 KB Output is correct
60 Correct 609 ms 159604 KB Output is correct
61 Correct 598 ms 159712 KB Output is correct
62 Correct 545 ms 159564 KB Output is correct
63 Correct 598 ms 151892 KB Output is correct
64 Correct 721 ms 153172 KB Output is correct
65 Correct 594 ms 151884 KB Output is correct
66 Correct 207 ms 161108 KB Output is correct
67 Correct 562 ms 160220 KB Output is correct
68 Correct 433 ms 160188 KB Output is correct
69 Correct 290 ms 162692 KB Output is correct
70 Correct 461 ms 159572 KB Output is correct
71 Correct 628 ms 159896 KB Output is correct