Submission #701823

#	Time	Username	Problem	Language	Result	Execution time	Memory
701823		jiahng	Railway Trip 2 (JOI22_ho_t4)	C++14	16 / 100	2076 ms	281656 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 400010
#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[21];

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];

    FOR(i,0,20) root[i] = new node(1,N);
    FOR(i,1,M){
        if (A[i] < B[i]) root[0]->upd_mx(A[i],min(A[i] + K - 1, B[i]), B[i]);
        else root[0]->upd_mn(max(B[i], A[i] - K + 1), A[i], B[i]);
    }
    FOR(i,1,N) dp[i][0] = root[0]->qry(i,i);
    FOR(k,1,20){
        FOR(i,1,N) dp[i][k] = root[k-1]->qry(dp[i][k-1].f, dp[i][k-1].s);
        FOR(i,1,N) root[k]->upd_mn(i,i,dp[i][k].f), root[k]->upd_mx(i,i,dp[i][k].s);
    }
    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,20,0) {
            if (DEBUG) cout << cur.f << ' ' << cur.s << '\n';
            pi x = root[k]->qry(cur.f,cur.s);
            
            if (!(x.f <= T[i] && T[i] <= x.s)){
                ans += (1<<k);
                cur = x;
            }
        }
        pi x = root[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: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13