Submission #1245022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245022		M_SH_O	Railway Trip 2 (JOI22_ho_t4)	C++20	0 / 100	215 ms	60880 KiB

Main

/*#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")*/
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/

#define ll long long
#define ll1 long long
#define ull unsigned long long
#define dou long double
#define str string
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vbool vector<bool>
#define vstr vector<str>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
//#define endl "\n"
#define fr first
#define se second
// #define sortcmp(a) sort(a.begin(), a.end(), cmp)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define INF 1000000000000000007
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
//using namespace __gnu_pbds;

mt19937 rng(time(0));
ll randll(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

vpll tree;

pll get(ll l, ll r, ll v, ll tl, ll tr) {
    if (l <= tl && tr <= r) return tree[v];
    if (tl > r || tr < l) return {-INF, -1};

    ll tm = (tl+tr)/2;
    //push(v, tl, tr);
    pll p = get(l, r, v*2, tl, tm), p1 = get(l, r, v*2+1, tm+1, tr);
    return max(p,p1);
}


void update(ll idx, pll val, ll v, ll tl, ll tr) {
    if (tl == tr) {
        tree[v] = max(tree[v], val);
        return;
    }

    ll tm = (tl+tr)/2;
    //push(v, tl, tr);

    if (idx <= tm)update(idx, val, v*2, tl, tm);
    else update(idx, val, v*2+1, tm+1, tr);

    tree[v] = max(tree[v*2], tree[v*2+1]);
}

vll p, c;
vvll g, pr;
vbool us;

void dfs(ll v) {
    for(int i = 0; (1 << i) <= c.size(); i ++){
        pr[v][i] = c[c.size()-(1 <<i)];
    }
    c.pb(v);
    us[v] = 1;
    for(int i : g[v]){
        if(!us[i]) dfs(i);
    }
    
    c.pop_back();
}

int main(){
    speed;
    srand(time(0));

    ll n, k, m;
    cin >> n >> k;
    cin >> m;
    p.resize(m, -1);
    pr.resize(m, vll(20, -1));
    vpll a(m);
    for (int i = 0; i < m; i ++) {
        cin >> a[i].fr >> a[i].se;
    }

    sort(a);
    tree.resize(n*4+7, {-INF, -1});
    g.resize(m+7);
    for (int i = m-1; i >= 0; i --) {
        ll x = get(a[i].fr, a[i].se, 1, 0, n).se;
        p[i] = x;
        if (x != -1) g[x].pb(i);
        update(a[i].fr, {a[i].se, i}, 1, 0, n);
    }
    
    us.resize(m+7, 0);
    vpll v1(n+7, {-1, -1});
    for(int i = m-1; i >= 0; i --){
        v1[a[i].fr] = max(v1[a[i].fr], {a[i].se, i});
        if(us[i]) continue;
        dfs(i);
    }
    
    vll v(n+7, -1);
    multiset<pll> s;
    
    for(int i = 1; i <= n; i ++){
        s.insert(v1[i]);
        if(i-k >= 1) s.erase(s.find(v1[i-k]));
        v[i] = (*--s.end()).se;
    }
    /*for(int i = 0; i < m; i ++){
        cout << a[i].fr << ' ' << a[i].se << endl;
    }
    
    for(int i = 0; i < m; i ++){
        for(int j = 0; j < 3; j ++){
            cout << pr[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;*/
    
    ll q;
    cin >> q;
    
    while(q --){
        ll a1, b;
        cin >> a1 >> b;
        if(v[a1] == -1){
            cout << -1 << endl;
            continue;
        }
        if(a[v[a1]].se >= b){
            cout << 1 <<  endl;
            continue;
        }
        ll res = 0, x = v[a1];
        //cout << x << endl;
        //cout << "!" << endl;
        for(int i = 19; i >= 0; i --){
            //cout << x << ' ' << pr[x][i] << endl;
            if(pr[x][i] == -1 || a[pr[x][i]].se >= b) continue;
            //cout << i << endl;
            res += 1 << i;
            x = pr[x][i];
        }
       // cout << "! " << x << endl;
        if(a[pr[x][0]].se >= b){
            cout << res+2 << endl;
        }
        else cout << -1 << endl;
    }
}

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