제출 #697807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697807		Duy_e	Event Hopping (BOI22_events)	C++14	25 / 100	1599 ms	51056 KiB

events

#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define st first
#define nd second
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;

const long long INF = 1e18;
const long long N = 1e5 + 5;

ll n, q, s[N], e[N];
vector <int> cmp, out[2 * N], in[2 * N];
vector <int> d[N];

const ll Nmax = 5005;
int dist[Nmax][Nmax];
void bfs(int st, int *f) {
    rep(i, 1, n) f[i] = 1e9;
    f[st] = 0;
    queue <int> q;
    q.push(st);
    while (q.size()) {
        int u = q.front(); q.pop();
        for (int v: d[u]) if (f[v] > f[u] + 1) {
            f[v] = f[u] + 1;
            q.push(v);
        }
    }
}

namespace sub4 {

    pii a[N];
    ll pos[N], f[N];
    void solve() {
        rep(i, 1, n) a[i] = {e[i], i};
        sort(a + 1, a + 1 + n);
        rep(i, 1, n) pos[a[i].nd] = i;
        while (q --) {
            int u, v;
            cin >> u >> v;
            int i = pos[u];
            int j = pos[v];
            int l = j;

            if (i > j && a[j].st < a[i].st) {
                cout << "impossible\n";
                continue;
            }

            if (i > j) {
                cout << 1 << '\n';
                continue;
            }

            while (l + 1 <= n && a[l + 1].st == a[j].st) l ++;

            f[l + 1] = 1e9;
            //cout << i << ' ' << j << '\n';
            rrep(k, l, i) {
                int id = a[k].nd;
                f[k] = min(f[k + 1], s[id]);
            }
            int ans = 0;
            while (i < j) {
                ans ++;
                int cur = a[i].st, pre = i;
                while (i < l && cur >= f[i + 1]) {
                    i ++;
                }
                if (i > j) {
                    int id = a[j].nd;
                    if (cur >= s[v] && cur <= e[v])
                        break;
                    ans ++;
                    break;
                }
                if (i == pre) break;

            }

            //cout << i << ' ' << j << '\n';

            if (i >= j)
                cout << ans << '\n';
            else
                cout << "impossible\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> q;
    rep(i, 1, n)
        cin >> s[i] >> e[i];

    if (q <= 100) {
        sub4 :: solve();
        return 0;
    }

    rep(i, 1, n) rep(j, 1, n) if (i != j)
        if (s[j] <= e[i] && e[i] <= e[j])
            d[i].push_back(j);

    rep(i, 1, n) bfs(i, dist[i]);

    while (q --) {
        int u, v;
        cin >> u >> v;
        if (dist[u][v] >= (int)1e9)
            cout << "impossible\n";
        else
            cout << dist[u][v] << '\n';
    }

    return 0;
}

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

events.cpp: In function 'void sub4::solve()':
events.cpp:74:25: warning: unused variable 'id' [-Wunused-variable]
   74 |                     int id = a[j].nd;
      |                         ^~

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