Submission #701838

#	Time	Username	Problem	Language	Result	Execution time	Memory
701838		jiahng	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	899 ms	349840 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ll int
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 200010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
#define DEBUG 0

struct node{
    int s,e,m,mx,mn,lazy_mx=-INF,lazy_mn=INF;
    node *l,*r;

    node(int ss,int ee){
        s = ss; e = ee; m = (s + e) / 2;
        mx = e; mn = s;
        if (s != e){
             l = new node(s,m); r = new node(m+1,e);
        }
    }
    void prop(){
        if (s == e) return;
        l->lazy_mx = max(l->lazy_mx, lazy_mx);
        r->lazy_mx = max(r->lazy_mx, lazy_mx);
        l->mx = max(l->mx, lazy_mx);
        r->mx = max(r->mx, lazy_mx);

        l->lazy_mn = min(l->lazy_mn, lazy_mn);
        r->lazy_mn = min(r->lazy_mn, lazy_mn);
        l->mn = min(l->mn, lazy_mn);
        r->mn = min(r->mn, lazy_mn);

        lazy_mn = INF, lazy_mx = -INF;
    }

            
    void upd_mx(int a,int b,int c){
        prop();
        if (a <= s && e <= b){
            mx = max(mx, c);
            lazy_mx = max(lazy_mx, c);
        }else if (a > e || s > b) return;
        else{
            l->upd_mx(a,b,c); r->upd_mx(a,b,c);
            mx = max(l->mx, r->mx);
        }

    }
    void upd_mn(int a,int b,int c){
        prop();
        if (a <= s && e <= b){
            mn = min(mn, c);
            lazy_mn = min(lazy_mn, c);
        }else if (a > e || s > b) return;
        else{
            l->upd_mn(a,b,c); r->upd_mn(a,b,c);
            mn = min(l->mn, r->mn);
        }
    }

    pi qry(int a,int b){
        prop();
        if (a <= s && e <= b) return pi(mn, mx);
        else if (a > e || s > b) return pi(INF, -INF);
        else{
            pi x = l->qry(a,b), y = r->qry(a,b);
            return pi(min(x.f,y.f), max(x.s,y.s));
        }
    }
}*root;

inline int lg2(int x){
    return 31 - __builtin_clz(x);
}
struct SparseTable{
    int table[maxn][20];
    int N;
    bool mn;

    SparseTable(vi &v, bool _mn){
        N = v.size();
        mn = _mn;
        FOR(i,0,v.size()-1) table[i+1][0] = v[i];
        FOR(k,1,19) FOR(i,1,N){
            if (mn){
                table[i][k] = min(table[i][k-1],table[min(i+(1<<(k-1)),N)][k-1]);
            }else{
                table[i][k] = max(table[i][k-1],table[min(i+(1<<(k-1)),N)][k-1]);
            }
        }
    }
    int qry(int a,int b){
        int x = lg2(b-a+1);
        if (mn) return min(table[a][x], table[b-(1<<x)+1][x]);
        else return max(table[a][x], table[b-(1<<x)+1][x]);
    }
}*min_table[20], *max_table[20];

int N,K,M,Q,A[maxn],B[maxn],S[maxn],T[maxn];
pi dp[maxn][21];
int32_t main(){
    fast;
    cin >> N >> K >> M;
    FOR(i,1,M) cin >> A[i] >> B[i];
    cin >> Q;
    FOR(i,1,Q) cin >> S[i] >> T[i];

    root = new node(1,N);

    FOR(i,1,M){
        if (A[i] < B[i]) root->upd_mx(A[i],min(A[i] + K - 1, B[i]), B[i]);
        else root->upd_mn(max(B[i], A[i] - K + 1), A[i], B[i]);
    }
    vi mn, mx;
    FOR(i,1,N){
        dp[i][0] = root->qry(i,i);
        mn.pb(dp[i][0].f); mx.pb(dp[i][0].s);
    }
    min_table[0] = new SparseTable(mn, 1);
    max_table[0] = new SparseTable(mx, 0);
    FOR(k,1,19){
        FOR(i,1,N) dp[i][k] = pi(min_table[k-1]->qry(dp[i][k-1].f, dp[i][k-1].s), max_table[k-1]->qry(dp[i][k-1].f, dp[i][k-1].s));
        vi mn,mx;
        FOR(i,1,N) mn.pb(dp[i][k].f), mx.pb(dp[i][k].s);
        min_table[k] = new SparseTable(mn,1);
        max_table[k] = new SparseTable(mx, 0);
    }
    if (DEBUG) FOR(i,1,N) cout << dp[i][0].f << ' ' << dp[i][0].s << '\n';

    FOR(i,1,Q){
        pi cur = pi(S[i],S[i]);
        int ans = 0;
        if (DEBUG) cout << "QUERY " << i << '\n';
        DEC(k,19,0) {
            if (DEBUG) cout << cur.f << ' ' << cur.s << '\n';
            pi x = pi(min_table[k]->qry(cur.f,cur.s), max_table[k]->qry(cur.f,cur.s));
            
            if (!(x.f <= T[i] && T[i] <= x.s)){
                ans += (1<<k);
                cur = x;
            }
        }
        pi x = pi(min_table[0]->qry(cur.f,cur.s), max_table[0]->qry(cur.f,cur.s));
        if (x.f <= T[i] && T[i] <= x.s) cout << ans+1 << '\n';
        else cout << -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