oj.uz

답안 #697954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697954 2023-02-11T15:09:13 Z Neos Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 128624 KB 
#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[N], e[N];

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]);


        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

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:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 448 KB Output is correct
2 Runtime error 3 ms 852 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 496 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 1 ms 464 KB Output is correct
18 Correct 1 ms 464 KB Output is correct
19 Execution timed out 1594 ms 128624 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 456 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 464 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Runtime error 4 ms 892 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 852 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 448 KB Output is correct
2 Runtime error 3 ms 852 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -