Submission #634662

#	Time	Username	Problem	Language	Result	Execution time	Memory
634662		someone	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	434 ms	156452 KiB

Main

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

struct Node {
    int deb, fin, mini, maxi;
};

const int T = 17, M = 1 << T, N = 2 * M;

int n, m, k, q;
Node node[T][N];
vector<int> deb[M], fin[M];

pair<int, int> getInter(int iTree, int d, int f) {
    //cout << d << ' ' << f << '\n';
    int l = d, r = f;

    d += M-1, f += M;
    while(d + 1 < f) {
        if(f & 1) {
            l = min(l, node[iTree][f - 1].mini);
            r = max(r, node[iTree][f - 1].maxi);
            //cout << ' ' << f-1 << ' ' << node[iTree][f - 1].mini << ' ' << node[iTree][f - 1].maxi << '\n';
        }
        if(!(d & 1)) {
            l = min(l, node[iTree][d + 1].mini);
            r = max(r, node[iTree][d + 1].maxi);
            //cout << ' ' << d+1 << ' ' << node[iTree][d + 1].mini << ' ' << node[iTree][d + 1].maxi << '\n';
        }
        d >>= 1;
        f >>= 1;
    }

    return {l, r};
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout.tie(0);

    cin >> n >> k >> m;
    for(int i = 0; i < M; i++)
        node[0][i + M].deb = i,
        node[0][i + M].fin = i+1;
    for(int i = M-1; i > 0; i--)
        node[0][i].deb = node[0][i*2].deb,
        node[0][i].fin = node[0][i*2+1].fin;
    for(int i = 1; i < N; i++)
        node[0][i].mini = node[0][i].deb,
        node[0][i].maxi = node[0][i].fin;
    for(int i = 1; i < T; i++)
        for(int j = 1; j < N; j++)
            node[i][j].deb = node[i-1][j].deb,
            node[i][j].fin = node[i-1][j].fin,
            node[i][j].mini = node[i-1][j].mini,
            node[i][j].maxi = node[i-1][j].maxi;

    for(int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        if(a < b) {
            fin[a].push_back(b+1);
            if(a + k <= n)
                fin[a + k].push_back(-b-1);
        } else {
            deb[a].push_back(b);
            if(a - k > 0)
                deb[a - k].push_back(-b);
        }
    }
    deque<int> mini, maxi;
    for(int i = 1; i <= n; i++) {
        for(int upd : fin[i]) {
            if(upd < 0) {
                if(!maxi.empty() && maxi[0] == -upd)
                    maxi.pop_front();
            } else {
                while(!maxi.empty() && maxi.back() < upd)
                    maxi.pop_back();
                maxi.push_back(upd);
            }
        }
        if(!maxi.empty())
            node[0][i + M].maxi = max(node[0][i + M].maxi, maxi[0]);
    }
    for(int i = n; i > 0; i--) {
        for(int upd : deb[i]) {
            if(upd < 0) {
                if(!mini.empty() && mini[0] == -upd)
                    mini.pop_front();
            } else {
                while(!mini.empty() && mini.back() > upd)
                    mini.pop_back();
                mini.push_back(upd);
            }
        }
        if(!mini.empty())
            node[0][i + M].mini = min(node[0][i + M].mini, mini[0]);
    }
    for(int i = M-1; i > 0; i--)
        node[0][i].mini = min(node[0][i*2].mini, node[0][i*2+1].mini),
        node[0][i].maxi = max(node[0][i*2].maxi, node[0][i*2+1].maxi);

    for(int i = 1; i < T; i++) {
        for(int j = 1; j <= n; j++) {
            pair<int, int> inter = getInter(i-1, node[i-1][j + M].mini, node[i-1][j + M].maxi);
            node[i][j + M].mini = inter.first,
            node[i][j + M].maxi = inter.second;
            //cout << j << ' ' << inter.first << ' ' << inter.second << '\n';
        }
        for(int j = M-1; j > 0; j--)
            node[i][j].mini = min(node[i][j*2].mini, node[i][j*2+1].mini),
            node[i][j].maxi = max(node[i][j*2].maxi, node[i][j*2+1].maxi);
    }

    cin >> q;
    for(int i = 0; i < q; i++) {
        int s, t; cin >> s >> t;

        int l = s, r = s + 1, nb = 0;
        for(int j = T-1; j > -1; j--) {
            pair<int, int> inter = getInter(j, l, r);
            if(t < inter.first || inter.second <= t) {
                nb += (1 << j);
                l = inter.first, r = inter.second;
            }
        }
        if(nb + 1 == (1 << T))
            cout << "-1\n";
        else
            cout << nb+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