Submission #1171185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171185		KhanhDang	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	544 ms	51868 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define     ll long long
#define    pll pair<ll, ll>
#define    pii pair<int, int>
#define     fi first
#define     se second
#define all(v) (v).begin(),(v).end()
#define Unique(v) sort(all(v)); (v).erase(unique(all(v)), (v).end());
const int N = 1e5 + 5;
int n, k, m, q;
int L[20][N], R[20][N];
pii st[20][4 * N];
pii GET(pii a, pii b) {
    return {min(a.fi, b.fi), max(a.se, b.se)};
}
void build(int lg, int id, int l, int r) {
    if (l == r) {
        st[lg][id] = {L[lg][l], R[lg][l]};
        return;
    }
    int mid = l + r >> 1;
    build(lg, id << 1, l, mid);
    build(lg, id << 1 | 1, mid + 1, r);

    st[lg][id] = GET(st[lg][id << 1], st[lg][id << 1 | 1]);
}
pii get(int lg, int id, int l, int r, int u, int v) {
    if (v < l || r < u) return {n + 1, 0};
    if (u <= l && r <= v) return st[lg][id];

    int mid = l + r >> 1;
    return GET(get(lg, id << 1, l, mid, u, v), get(lg, id << 1 | 1, mid + 1, r, u, v));
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "task"
    if (fopen(task".INP", "r")) {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }
    if (fopen("task.INP", "r")) {
        freopen("task.INP", "r", stdin);
        freopen("task.OUT", "w", stdout);
    }
    cin>>n>>k>>m;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 18; j++)
            L[j][i] = R[j][i] = i;
    for (int i = 1; i <= m; i++) {
        int a, b; cin>>a>>b;
        L[0][a] = min(L[0][a], b);
        R[0][a] = max(R[0][a], b);
    }
    build(0, 1, 1, n);
    for (int i = 1; i <= n; i++) {
        auto [u, v] = get(0, 1, 1, n, max(1, i - k + 1), i);
        R[0][i] = v;
        auto [x, y] = get(0, 1, 1, n, i, min(n, i + k - 1));
        L[0][i] = x;
    }
    build(0, 1, 1, n);
    for (int lg = 1; lg < 18; lg++) {
        for (int i = 1; i <= n; i++) {
            auto [u, v] = get(lg - 1, 1, 1, n, L[lg - 1][i], R[lg - 1][i]);
            L[lg][i] = u; R[lg][i] = v;
        }
        build(lg, 1, 1, n);
    }
    cin>>q;
    while (q--) {
        int s, t; cin>>s>>t;
        int _l = s, _r = s;
        int ans = 0;
        for (int i = 17; i >= 0; i--) {
            auto [u, v] = get(i, 1, 1, n, _l, _r);
            if (t < u || v < t) {
                ans += 1 << i;
                _l = u, _r = v;
            }
        }
        auto [u, v] = get(0, 1, 1, n, _l, _r);
        if (u <= t && t <= v) cout<<ans + 1<<'\n';
        else cout<<-1<<'\n';
    }
    cerr<<setprecision(3)<<fixed<<"Time elapsed: "<< 1.0 * clock() / CLOCKS_PER_SEC <<"s\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen("task.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen("task.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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