제출 #1098248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098248		rifat414141	Event Hopping (BOI22_events)	C++17	100 / 100	104 ms	31556 KiB

events

#include <bits/stdc++.h>
#define int long long int
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e18;
const int LOGN = 20;
int arr[N];
pair<int, int> segment_tree[4 * N];
int up[N][LOGN];
int par[N];
void build(int id, int l, int r)
{
    if (l == r)
    {
        segment_tree[id] = {arr[l - 1], l - 1};
        return;
    }
    int mid = (l + r) / 2;
    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);
    segment_tree[id] = min(segment_tree[2 * id], segment_tree[2 * id + 1]);
    return;
}
pair<int, int> range(int id, int l, int r, int L, int R)
{
    if (R < l || L > r)
    {
        return {INF, INF};
    }
    if (L <= l && r <= R)
    {
        return segment_tree[id];
    }
    int mid = (l + r) / 2;
    pair<int, int> x = range(2 * id, l, mid, L, R);
    pair<int, int> y = range(2 * id + 1, mid + 1, r, L, R);
    return min(x, y);
}
// struct Seg
// {
//     int siz;
//     vector<pair<int, int>> v;

//     void init(int n)
//     {
//         siz = 1;
//         while (siz < n)
//             siz *= 2;
//         v.assign(siz * 2, make_pair(INF, -1));
//     }

//     pair<int, int> merge(pair<int, int> x, pair<int, int> y)
//     {
//         pair<int, int> res;
//         res.first = min(x.first, y.first);
//         if (x.first == y.first)
//             res.second = min(x.second, y.second);
//         else if (res.first == x.first)
//             res.second = x.second;
//         else
//             res.second = y.second;
//         return res;
//     }

//     void set(int i, pair<int, int> p, int x, int lx, int rx)
//     {
//         if (rx - lx == 1)
//         {
//             v[x] = merge(p, v[x]);
//             return;
//         }
//         int m = (lx + rx) / 2;
//         if (i < m)
//             set(i, p, 2 * x + 1, lx, m);
//         else
//             set(i, p, 2 * x + 2, m, rx);
//         v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
//     }

//     void set(int i, pair<int, int> p)
//     {
//         set(i, p, 0, 0, siz);
//     }

//     pair<int, int> range_mx(int l, int r, int x, int lx, int rx)
//     {
//         if (l >= rx || lx >= r)
//             return make_pair(INF, -1);
//         if (lx >= l && rx <= r)
//             return v[x];
//         int m = (lx + rx) / 2;
//         return merge(range_mx(l, r, 2 * x + 1, lx, m), range_mx(l, r, 2 * x + 2, m, rx));
//     }

//     pair<int, int> range_mx(int l, int r)
//     {
//         return range_mx(l, r, 0, 0, siz);
//     }
// };
void solve()
{
    int n, q;
    cin >> n >> q;
    vector<pair<int, int>> v1;
    vector<pair<int, pair<int, int>>> v2;
    for (int i = 0; i < n; ++i)
    {
        int l, r;
        cin >> l >> r;
        v1.push_back({l, r});
        v2.push_back({r, {l, i}});
    }
    int brr[n], crr[n];
    sort(v2.begin(), v2.end());
    for (int i = 0; i < n; ++i)
    {
        arr[i] = v2[i].second.first;
        brr[v2[i].second.second] = i;
        crr[i] = v2[i].second.second;
    }
    build(1, 1, n);
    // Seg st;
    // st.init(n + 1);
    // for (int i = n - 1; i >= 0; i--)
    // {
    //     st.set(i, make_pair(v2[i].second.first, i));
    // }

    for (int i = 0; i < n; ++i)
    {
        pair<int, pair<int, int>> p = {v2[i].second.first, {-1, -1}};
        int it = lower_bound(v2.begin(), v2.end(), p) - v2.begin();
        // cout << v2[i].first << ' ' << it << endl;
        if (it == i)
        {
            up[i][0] = par[i] = i;
        }
        else
        {
            auto idx = range(1, 1, n, it + 1, i + 1);
            up[i][0] = par[i] = idx.second;
        }
    }
    for (int j = 1; j < LOGN; ++j)
    {
        for (int i = 0; i < n; ++i)
        {
            if (j == 1)
                up[i][j] = up[par[i]][j - 1];
            else
                up[i][j] = up[up[i][j - 1]][j - 1];
            // up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    while (q--)
    {
        int s, e;
        cin >> s >> e;
        if (s == e)
        {
            cout << 0 << endl;
            continue;
        }
        s--, e--;
        int ogs = brr[s], oge = brr[e];
        int sl = v2[ogs].second.first, sr = v2[ogs].first;
        int el = v2[oge].second.first, er = v2[oge].first;
        if (ogs > oge)
        {
            if (sr >= el && sr <= er)
            {
                cout << 1 << endl;
                continue;
            }
            else
            {
                cout << "impossible" << endl;
                continue;
            }
        }
        int curr = oge;
        int ans = 0;
        int mn = sr;
        for (int i = LOGN - 1; i >= 0; --i)
        {
            if (v2[up[curr][i]].second.first > mn)
            {
                ans += (1 << i);
                curr = up[curr][i];
            }
        }
        if (v1[crr[curr]].first > mn)
        {
            ans++;
            curr = up[curr][0];
        }
        // cout << curr << endl;
        ans++;
        // curr = up[curr][0];
        if (v1[crr[curr]].first > mn)
        {
            cout << "impossible" << endl;
            continue;
        }
        else
        {
            cout << ans << endl;
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("prime_subtractorization_input.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int t = 1;
    // cin >> t;
    for (int tt = 1; tt <= t; ++tt)
    {
        // cout << "Case #" << tt << ": ";
        solve();
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

events.cpp: In function 'void solve()':
events.cpp:167:13: warning: unused variable 'sl' [-Wunused-variable]
  167 |         int sl = v2[ogs].second.first, sr = v2[ogs].first;
      |             ^~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30