Submission #884629

#	Time	Username	Problem	Language	Result	Execution time	Memory
884629		efedmrlr	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1812 ms	75676 KiB

Main

#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 21;
const int MOD = 1e9+7;
int n,m,q,K;

struct Interval {
    int l,r;
    Interval(int lf, int rg) {
        l = lf;
        r = rg;
    }
    Interval() {
        l = 0; r = 0;
    }
    bool check(int x) {
        return l<=x && x<=r;
    }
    void print() {
        cout<<"l:"<<l<<" r: "<<r<<"\n";
    }
}; 

struct RUPQ {
    vector<int> data;
    int sz;
    
    RUPQ(int sz) {
        this->sz = sz;
        data.assign(4*(sz + 5), -INF);
    }
    
    void update(int tl, int tr, int v, int l, int r, int val) {
        if(tl >= l && tr <= r) {
            data[v] = val;
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        int tm = (tl + tr) >> 1;
        update(tl, tm, v*2, l, r, val);
        update(tm + 1, tr, v*2+1, l, r, val);
    }
    void update(int l, int r, int val) {
        update(0, sz, 1, l, r, val);
    }
    int query(int tl, int tr, int v, int ind) {
        if(tl == tr) {
            return data[v];
        }
        int tm = (tl + tr) >> 1;
        if(ind <= tm) {
            return max(data[v], query(tl, tm, v*2, ind));
        }
        else {
            return max(data[v], query(tm + 1, tr, v*2+1, ind));
        }
    }
    int query(int ind) {
        return query(0, sz, 1, ind);
    }

};

struct PURQ {
    int sz;
    vector<int> data;
    PURQ(int sz) {
        this->sz = sz;
        data.assign(4* (sz + 5), -INF);
    }
    void update(int tl, int tr, int v, int ind, int val) {
        if(tl == tr) {
            data[v] = max(data[v], val);
            return;
        }
        int tm = (tl + tr) >> 1;
        if(ind <= tm) {
            update(tl, tm, v*2, ind, val);
        }
        else {
            update(tm + 1, tr, v*2+1, ind, val);
        }
        data[v] = max(data[v*2], data[v*2+1]);
    }
    void update(int ind ,int val) {
        update(0, sz, 1, ind, val);
    }
    int query(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            return data[v];
        }
        if(tl > r || tr < l) {
            return -INF;
        }
        int tm = (tl + tr) >> 1;
        return max(query(tl, tm, v*2, l, r), query(tm + 1, tr, v*2+1, l, r));
    }
    int query(int l, int r) {
        return query(0, sz, 1, l, r);
    }

};



vector<array<int,2> > trainl, trainr;   //trainl -l, r  //  trainr r l
PURQ *lft[LGN], *rgt[LGN];  //left - || right +

void prec() {
    RUPQ dsr(n), dsl(n);
    sort(trainr.begin(), trainr.end());
    sort(trainl.begin(), trainl.end());
    
    for(auto c : trainr) {
        dsr.update(c[1] , min(c[1] + K - 1, c[0]), c[0]);
    }

    for(auto c : trainl) {
        dsl.update(max(c[1] - K + 1, -c[0]), c[1], c[0]);
    }
    
    for(int i = 1; i<=n; i++) {
        // Interval tmp(max(dsl.query(i), -i), max(dsr.query(i), i));
        // tmp.l *= -1;
        // cout<<"i:"<<i<<" "; 
        // tmp.print();
        rgt[0]->update(i, max(dsr.query(i), i));
        lft[0]->update(i, max(dsl.query(i), -i));
    }
    for(int k = 1; k<LGN; k++) {
        // cout<<"k:"<<k<<"\n";
        for(int i = 1; i<=n; i++) {
            Interval cur(-lft[k - 1]->query(i,i), rgt[k - 1]->query(i,i));
            // cur.print();
            rgt[k]->update(i, rgt[k - 1]->query(cur.l, cur.r));
            lft[k]->update(i, lft[k - 1]->query(cur.l, cur.r));
        }
    }

    
}
Interval move_interval(Interval &x, int k) { //move interval by 2^k steps
    Interval tmp(-lft[k]->query(x.l, x.r), rgt[k]->query(x.l, x.r));
    return tmp;
}
int ans_query(int s, int t) {
    Interval cur(s,s);
    int ans = 0;
    for(int i = LGN - 1; i>=0; i--) {
        Interval nxt = move_interval(cur, i);
        if(!nxt.check(t)) {
            cur = nxt;
            ans += (1<<i);
        }  
    }
    ans++;
    cur = move_interval(cur, 0);
    if(cur.check(t)) {
        return ans;
    }
    return -1;

}

inline void solve() {
    cin>>n>>K;
    cin>>m;
    
    for(int i = 0; i<m; i++) {
        int l,r;
        cin >> l >> r;
        if(r > l) {
            trainr.pb({r,l});
        }
        else {
            trainl.pb({-r,l});
        }
    }
    cin>>q;
    for(int i = 0; i<LGN; i++) {
        lft[i] = new PURQ(n);
        rgt[i] = new PURQ(n);
    }
    prec();
   
    for(int i = 1; i<=q; i++) {
        int s,t;
        cin>>s>>t;
        cout<<ans_query(s,t)<<"\n";
    }

}
 
signed main() {
    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

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