Submission #936319

#	Time	Username	Problem	Language	Result	Execution time	Memory
936319		qwe1rt1yuiop1	Railway Trip 2 (JOI22_ho_t4)	C++14	27 / 100	2039 ms	132296 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
// #define int long long
using namespace std;
using pii = pair<int, int>;

// vector<vector<int>> segl, segr, tagl, tagr;
vector<int> segl[20], segr[20], tagl[20], tagr[20];

inline void pushl(int id, int x, int l, int r)
{
    if (tagl[id][x] == 1e9)
        return;
    segl[id][x] = tagl[id][x];
    if (l + 1 != r)
        tagl[id][x << 1] = tagl[id][x << 1 | 1] = tagl[id][x];
    tagl[id][x] = 1e9;
}
inline void updl(int id, int x, int l, int r, int ql, int qr, int k)
{
    pushl(id, x, l, r);
    if (qr <= l || r <= ql)
        return;
    if (ql <= l && r <= qr)
    {
        tagl[id][x] = k;
        pushl(id, x, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    updl(id, x << 1, l, mid, ql, qr, k);
    updl(id, x << 1 | 1, mid, r, ql, qr, k);
    segl[id][x] = min(segl[id][x << 1], segl[id][x << 1 | 1]);
}
inline int qryl(int id, int x, int l, int r, int ql, int qr)
{
    pushl(id, x, l, r);
    if (qr <= l || r <= ql)
        return 1e9;
    if (ql <= l && r <= qr)
        return segl[id][x];
    int mid = (l + r) >> 1;
    return min(qryl(id, x << 1, l, mid, ql, qr), qryl(id, x << 1 | 1, mid, r, ql, qr));
}
inline void pushr(int id, int x, int l, int r)
{
    if (tagr[id][x] == -1e9)
        return;
    segr[id][x] = tagr[id][x];
    if (l + 1 != r)
        tagr[id][x << 1] = tagr[id][x << 1 | 1] = tagr[id][x];
    tagr[id][x] = -1e9;
}
inline void updr(int id, int x, int l, int r, int ql, int qr, int k)
{
    pushr(id, x, l, r);
    if (qr <= l || r <= ql)
        return;
    if (ql <= l && r <= qr)
    {
        tagr[id][x] = k;
        pushr(id, x, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    updr(id, x << 1, l, mid, ql, qr, k);
    updr(id, x << 1 | 1, mid, r, ql, qr, k);
    segr[id][x] = max(segr[id][x << 1], segr[id][x << 1 | 1]);
}
inline int qryr(int id, int x, int l, int r, int ql, int qr)
{
    pushr(id, x, l, r);
    if (qr <= l || r <= ql)
        return -1e9;
    if (ql <= l && r <= qr)
        return segr[id][x];
    int mid = (l + r) >> 1;
    return max(qryr(id, x << 1, l, mid, ql, qr), qryr(id, x << 1 | 1, mid, r, ql, qr));
}

inline void solve()
{
    int n, k, m;
    cin >> n >> k >> m;
    vector<pii> v(m);
    for (auto &[a, b] : v)
        cin >> a >> b, --a, --b;
    
    segl[0].assign(n * 4 + 5, 1e9);
    segr[0].assign(n * 4 + 5, -1e9);
    for (int i = 0; i < 20; ++i)
    {
        tagl[i] = segl[i] = segl[0];
        tagr[i] = segr[i] = segr[0];
    }

    for (int i = 0; i < n; ++i)
    {
        updl(0, 1, 0, n, i, i + 1, i);
        updr(0, 1, 0, n, i, i + 1, i);
    }

    vector<array<int, 3>> opl, opr;
    array<int, 3> tmp;
    for (auto [a, b] : v)
    {
        if (a < b)
            opr.emplace_back(tmp = {b, a, min(a + k, b)});
        else
            opl.emplace_back(tmp = {b, max(a - k, b) + 1, a + 1});
    }
    sort(opl.begin(), opl.end());
    sort(opr.begin(), opr.end());
    reverse(opl.begin(), opl.end());
    for (auto [a, b, c] : opl)
        updl(0, 1, 0, n, b, c, a);
    for (auto [a, b, c] : opr)
        updr(0, 1, 0, n, b, c, a);

    for (int i = 1; i < 20; ++i)
        for (int j = 0; j < n; ++j)
        {
            int mn = qryl(i - 1, 1, 0, n, j, j + 1);
            int mx = qryr(i - 1, 1, 0, n, j, j + 1);
            updl(i, 1, 0, n, j, j + 1, qryl(i - 1, 1, 0, n, mn, mx + 1));
            updr(i, 1, 0, n, j, j + 1, qryr(i - 1, 1, 0, n, mn, mx + 1));
        }

    int q;
    cin >> q;
    while (q--)
    {
        int s, t;
        cin >> s >> t;
        --s, --t;
        if (t < qryl(19, 1, 0, n, s, s + 1) || qryr(19, 1, 0, n, s, s + 1) < t)
        {
            cout << "-1\n";
            continue;
        }
        int ans = 0, ll = s, rr = s;
        for (int msk = 19; msk >= 0; --msk)
        {
            int mn = qryl(msk, 1, 0, n, ll, rr + 1);
            int mx = qryr(msk, 1, 0, n, ll, rr + 1);
            if (mn <= t && t <= mx)
                continue;
            ans += (1 << msk);
            ll = mn, rr = mx;
        }
        cout << ans + 1 << '\n';
    }
}

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

    solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:87:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |     for (auto &[a, b] : v)
      |                ^
Main.cpp:106:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |     for (auto [a, b] : v)
      |               ^
Main.cpp:116:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |     for (auto [a, b, c] : opl)
      |               ^
Main.cpp:118:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |     for (auto [a, b, c] : opr)
      |               ^

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