Submission #697958

#	Time	Username	Problem	Language	Result	Execution time	Memory
697958		Neos	Event Hopping (BOI22_events)	C++14	25 / 100	1555 ms	128652 KiB

events

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

#define ar array
#define fi first
#define se second
#define sz(x) (int)x.size()
#define rep(i, b, e) for (int i = (b); i <= (e); i++)
#define rrep(i, b, e) for (int i = (b); i >= (e); i--)

typedef long long ll;
typedef pair<ll, ll> ii;

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 5e3 + 7, M = 1e5 + 7;

int n, q, s[M], e[M];

void read() {
    cin >> n >> q;
    rep(i, 1, n) cin >> s[i] >> e[i];
}

int d[N][N];
vector<int> adj[N];
void sub3() {
    rep(i, 1, n) rep(j, 1, n) {
        if (s[j] <= e[i] && e[i] <= e[j]) {
            adj[i].push_back(j);
        }
    }

    memset(d, -1, sizeof d);
    rep(i, 1, n) {
        queue<int> q;
        q.push(i); d[i][i] = 0;
        while (sz(q)) {
            int u = q.front(); q.pop();
            for (int v: adj[u]) if (d[i][v] == -1) {
                d[i][v] = d[i][u] + 1;
                q.push(v);
            }
        }
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        (d[l][r] == -1 ? cout << "impossible\n" : cout << d[l][r] << '\n');
    }
}

int mn[M];
map<ii, int> pos;

int jump(int cur, int st, int des) {
    int l = st, r = des, ans = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (mn[mid] > cur) r = mid - 1;
        else l = mid + 1, ans = mid;
    }
    return ans;
}

void sub4() {
    vector<ii> vec;
    rep(i, 1, n) vec.push_back({e[i], i});
    sort(vec.begin(), vec.end(), [&](ii x, ii y){
         return (x.fi == y.fi ? s[x.se] < s[y.se] : x.fi < y.fi);
    });
    rep(i, 0, n - 1) pos[{vec[i].fi, vec[i].se}] = i;

    for (int u, v; q; q--) {
        cin >> u >> v;

        int l = pos[{e[u], u}], r = pos[{e[v], v}], ans = 0, ok = 1;
        int cur = e[u];

        mn[r] = s[vec[r].se];
        rrep(i, r - 1, l) mn[i] = min(mn[i + 1], s[vec[i].se]);

        if (u == v) {
            cout << "0\n";
            continue;
        }
        if (s[v] <= cur && cur <= e[v]) {
            cout << 1 << '\n';
            continue;
        }
        while (cur <= s[v]) {
            int nxt = jump(cur, l + 1, r);
            if (l != r && s[v] <= cur && cur <= e[v]) {
                l = r;
                ans++;
                break;
            }
            if (nxt == -1) {
                ok = 0;
                break;
            }
            ans++; cur = vec[nxt].fi; l = nxt;
        }
        if (l != r) ans++;
        if (l > r|| !ok) cout << "impossible\n";
        else cout << ans << '\n';
    }
}

void solve() {
    if (q <= 100) sub4();
    else if (n <= 5000) sub3();
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    read();
    solve();
}


/**
+ check mod (gõ đúng số), limit, kiểu dữ liệu
+ check format output
+mấy bài multitest:
    quên reset biến, mảng, (nên dùng fill, memset, v.v)
    quên xuống dòng
    precompute đầu bài
+nhập hết dữ liệu trước khi return
+xóa debug
**/

Compilation message (stderr)

events.cpp: In function 'int jump(int, int, int)':
events.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~
events.cpp: In function 'int main()':
events.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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