Submission #998013

#	Time	Username	Problem	Language	Result	Execution time	Memory
998013		Otalp	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	634 ms	510816 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define ld long double
#define pb push_back

pii a[200100];
pii c[200100][25][25];
int dp[200100], us[200100];
vector<int> dq[200100];
int lg[200100];


pii get(int l, int r, int k){
    int h = lg[r - l + 1];
    return {min(c[l][k][h].ff, c[r-(1 << h) + 1][k][h].ff), max(c[l][k][h].ss, c[r-(1 << h) + 1][k][h].ss)};
}


void solve(){
    int n, k;
    cin>>n>>k;
    int m;

    cin>>m;
    lg[1] = 0;
    for(int i=2; i<=n; i++){
        lg[i] = lg[i / 2] + 1; 
    }
    for(int i=1; i<=m; i++){
        cin>>a[i].ff>>a[i].ss;
        if(a[i].ff < a[i].ss){
            dq[a[i].ff].pb(a[i].ss);
            dq[min(a[i].ff + k, a[i].ss + 1)].pb(-a[i].ss);
        }
        if(a[i].ff > a[i].ss){
            dq[max(a[i].ff - k + 1, a[i].ss)].pb(a[i].ss);
            dq[a[i].ff + 1].pb(-a[i].ss);
        }
    }
    multiset<int> dd;
    for(int i=1; i<=n; i++){
        //cout<<"##############\n";
        //cout<<i<<'\n';
        for(int h: dq[i]){
            //cout<<h<<' ';
            if(h > 0) dd.insert(h);
            else dd.erase(dd.find(-h));
        }
        //cout<<'\n';
        int l=i, r=i;
        if(dd.size()){
            l = min(l, *dd.begin());
            r = max(r, *dd.rbegin());
        }
        c[i][0][0] = {l, r};
    }
    for(int k=1; k<=20; k++){
        for(int h=1; h<=20; h++){
            for(int i=1; i<=n; i++){
                if(i + (1 << h) - 1 > n){
                    break;
                } 
                c[i][k-1][h] = {min(c[i][k-1][h-1].ff, c[i+(1 << h - 1)][k-1][h-1].ff), max(c[i][k-1][h-1].ss, c[i+(1 << h - 1)][k-1][h-1].ss)};
            }
        }
        for(int i=1; i<=n; i++){
            pii h = get(c[i][k-1][0].ff, c[i][k - 1][0].ss, k - 1);
            c[i][k][0] = h;
        }
    }
    //for(int i=1; i<=n; i++){
        //cout<<c[i].ff<<' '<<c[i].ss<<'\n';
    //}
    int t;
    cin>>t;
    while(t--){
        int s, f;
        cin>>s>>f;
        //cout<<s<<' '<<f<<'\n';
        int l=s, r=s;
        int res = 0;
        if(c[s][20][0].ff > f or c[s][20][0].ss < f){
            cout<<-1<<'\n';
            continue;
        }
        for(int i=20; i>=0; i--){
            pii h = get(l, r, i);
            if(h.ff > f or h.ss < f) l = h.ff, r = h.ss, res += (1 << i);
        } 
        cout<<res + 1<<'\n';
    }
}


signed main(){
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:67:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   67 |                 c[i][k-1][h] = {min(c[i][k-1][h-1].ff, c[i+(1 << h - 1)][k-1][h-1].ff), max(c[i][k-1][h-1].ss, c[i+(1 << h - 1)][k-1][h-1].ss)};
      |                                                                  ~~^~~
Main.cpp:67:124: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   67 |                 c[i][k-1][h] = {min(c[i][k-1][h-1].ff, c[i+(1 << h - 1)][k-1][h-1].ff), max(c[i][k-1][h-1].ss, c[i+(1 << h - 1)][k-1][h-1].ss)};
      |                                                                                                                          ~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13