Submission #1268552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268552		lambd47	Railway Trip 2 (JOI22_ho_t4)	C++20	35 / 100	876 ms	122636 KiB

Main

#include <bits/stdc++.h>

#define int long long
using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int MOD=1e9+7;
const int MX=1e5+7;

struct seg{
    vector<int> mx,mn;
    int n;
    seg(){
        n=MX;
        mx=vector<int>(4*n,0);
        mn=vector<int>(4*n,MOD);
    }
    void update(int pos,int ini, int fim, int id, int val){
        if(ini>id || fim<id)return;
        if(ini==fim){
            mx[pos]=max(mx[pos],val);
            mn[pos]=min(mn[pos],val);
            return;
        }
        int m=(ini+fim)/2;
        update(2*pos,ini,m,id,val);
        update(2*pos+1,m+1,fim,id,val);
        mn[pos]=min(mn[2*pos],mn[2*pos+1]);
        mx[pos]=max(mx[2*pos],mx[2*pos+1]);
    }
    pair<int,int> query(int pos, int ini,int fim, int l, int r){
        if(ini>r || fim<l)return{MOD,0};
        if(l<=ini && fim<=r){
            return {mn[pos],mx[pos]};
        }
        int m=(ini+fim)/2;
        auto a=query(2*pos,ini,m,l,r);
        auto b=query(2*pos+1,m+1,fim,l,r);
        return {min(a.first,b.first),max(a.second,b.second)};
    }
};
const int lg=17;

void solve() {
    int n,m;cin>>n>>m;
    vector<seg> segs(lg);
    vector<vector<int>> vai(n);
    vector<vector<int>> volta(n);
    int k;cin>>k;
    L(i,0,n-1){
        segs[0].update(1,0,n-1,i,i);
    }
    L(i,0,k-1){
        int a,b;cin>>a>>b;
        a--;b--;
        if(a<b){
            vai[a].push_back(b);
            int x=min(a+m,b+1);
            if(x!=n)vai[x].push_back(n+b);
        }
        else{
            volta[a].push_back(b);
            int x=min(a-m,b-1);
            if(x>=0)volta[x].push_back(n+b);
        }
    }
    multiset<int> at;
    L(i,0,n-1){
        for(auto a:vai[i]){
            if(a>=n){
                at.erase(at.find(a-n));
            }
            else{
                at.insert(a);
            }
        }
        auto pt=at.end();
        if(!at.empty()){
            pt--;
            segs[0].update(1,0,n-1,i,*pt);
        }
    }
    at.clear();
    R(i,n-1,0){
        for(auto a:volta[i]){
            if(a>=n){
                at.erase(at.find(a-n));
            }
            else{
                at.insert(a);
            }
            if(!at.empty()){
                auto pt=at.begin();
                segs[0].update(1,0,n-1,i,*pt);
            }
        }
    }
    L(i,1,lg-1){
        L(j,0,n-1){
            auto b=segs[i-1].query(1,0,n-1,j,j);
            auto a=segs[i-1].query(1,0,n-1,b.first,b.second);
            segs[i].update(1,0,n-1,j,a.first);
            segs[i].update(1,0,n-1,j,a.second);
        }
    }
    int q;cin>>q;
    while(q--){
        int a,b;cin>>a>>b;
        a--;b--;
        int l=a;int r=a;
        if(a==b){
            cout<<0<<"\n";continue;
        }
        int resp=0;
        R(i,lg-1,0){
            auto p=segs[i].query(1,0,n-1,l,r);
            if(p.first<= b && b<= p.second){
                //deu certo ent resp<somando 
                continue;
            }
            else{
                l=p.first;
                r=p.second;
                resp+=(1<<i);
            }
        }
        if(resp>n){
            cout<<-1<<"\n";continue;
        }
        cout<<resp+1<<"\n";
    }







}
 
int32_t main() {
    std::cin.tie(0)->sync_with_stdio(0); 
    std::cin.exceptions(std::cin.failbit);

    int T = 1;
//    std::cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}

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