제출 #1288557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288557		Math4Life2020	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	316 ms	83124 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 131072; const ll E = 17; const ll INF = 1e18;

pii fz(pii p1, pii p2) {
    pii p3 = {min(p1.first,p2.first),max(p1.second,p2.second)};
    return p3;
}

ll l2(ll x) {
    if (x==0) return 100;
    return (31-__builtin_clz(x));
}

ll v2(ll x) {
    if (x==0) return 100;
    return __builtin_ctz(x);
}

//store: {min left, max right}
vector<pii> st0(2*Nm,{INF,-INF});

void pll(ll a, ll b, ll v) {
    if (a>b) return;
    ll la = v2(a); ll lb = v2(b+1);
    //cout << "pll call: "<<a<<","<<b<<"; v="<<v<<"\n";
    if (la<lb) {
        ll pt = (a>>la)+(1LL<<(E-la));
        //cout << "place at pt="<<pt<<"\n";
        st0[pt]=fz(st0[pt],{v,-INF});
        pll(a+(1LL<<la),b,v);
    } else {
        ll pt = (b>>lb)+(1LL<<(E-lb));
        //cout << "place at pt="<<pt<<"\n";
        st0[pt]=fz(st0[pt],{v,-INF});
        pll(a,b-(1LL<<lb),v);
    }
}

void plr(ll a, ll b, ll v) {
    if (a>b) return;
    ll la = v2(a); ll lb = v2(b+1);
    if (la<lb) {
        ll pt = (a>>la)+(1LL<<(E-la));
        st0[pt]=fz(st0[pt],{INF,v});
        plr(a+(1LL<<la),b,v);
    } else {
        ll pt = (b>>lb)+(1LL<<(E-lb));
        st0[pt]=fz(st0[pt],{INF,v});
        plr(a,b-(1LL<<lb),v);
    }
}

vector<pii> st1[E+2];

pii qry(ll a, ll b, ll e) {
    if (a>b) return {INF,-INF};
    ll la = v2(a); ll lb = v2(b+1);
    if (la<lb) {
        ll pt = (a>>la)+(1LL<<(E-la));
        //cout << "get: pt="<<pt<<", val="<<st1[e][pt].first<<", "<<st1[e][pt].second<<"\n";
        return fz(st1[e][pt],qry(a+(1LL<<la),b,e));
    } else {
        ll pt = (b>>lb)+(1LL<<(E-lb));
        //cout << "get: pt="<<pt<<", val="<<st1[e][pt].first<<", "<<st1[e][pt].second<<"\n";
        return fz(st1[e][pt],qry(a,b-(1LL<<lb),e));
    }
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N,K,M; cin >> N >> K >> M;
    for (ll i=0;i<N;i++) {
        pll(i,i,i);
        plr(i,i,i);
    }
    for (ll m=0;m<M;m++) {
        ll a,b; cin >> a >> b;
        a--; b--;
        //cout << "f1: a,b="<<a<<","<<b<<"\n";
        if (a<b) {
            ll rm = min(b-1,a+K-1);
            plr(a,rm,b);
        } else {
            ll lm = max(b+1,a-K+1);
            //cout << "f2\n";
            pll(lm,a,b);
        }
    }
    for (ll e=0;e<=(E+1);e++) {
        st1[e]=vector<pii>(2*Nm,{INF,-INF});
    }
    for (ll x=1;x<Nm;x++) {
        st0[2*x]=fz(st0[2*x],st0[x]);
        st0[2*x+1]=fz(st0[2*x+1],st0[x]);
    }
    for (ll x=(Nm-1);x>=1;x--) {
        st0[x]=fz(st0[2*x],st0[2*x+1]);
    }
    st1[0]=st0;
    //cout << st1[1][131072+2].first<< ", "<<st1[1][131072+2].second<<"\n";
    //qry(2,5,0); exit(0);
    for (ll e=0;e<=E;e++) {
        for (ll x=0;x<N;x++) {
            pii p0 = st1[e][x+Nm];
            pii p1 = qry(p0.first,p0.second,e);
            // if (x==2 && e==0) {
            //     cout << "p0: "<<p0.first<<","<<p0.second<<"\n";
            //     cout << "p1: "<<p1.first<<","<<p1.second<<"\n";
            // }
            st1[e+1][x+Nm]=p1;
        }
        for (ll p=(Nm-1);p>=1;p--) {
            st1[e+1][p]=fz(st1[e+1][2*p],st1[e+1][2*p+1]);
        }
    }
    //now binary search for the largest value that fails
    ll Q; cin >> Q;
    for (ll q=0;q<Q;q++) {
        ll s,t; cin >> s >> t; s--; t--;
        pii pmax = qry(s,s,E+1);
        if (pmax.first>t || t>pmax.second) {
            cout << "-1\n"; continue;
        }
        ll ans = 0;
        pmax = {s,s};
        for (ll e=E;e>=0;e--) {
            pii pnew = qry(pmax.first,pmax.second,e);
            if (pnew.first>t || t>pnew.second) {
                pmax = pnew; ans += (1LL<<e);
            }
        }
        cout << (ans+1) << "\n";
    }
}

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