oj.uz

답안 #697945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697945 2023-02-11T14:39:16 Z Neos Event Hopping (BOI22_events) C++14
0 / 100
 1500 ms 724 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;

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[N];
map<int, 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] = i;

    mn[n - 1] = s[vec.back().se];
    rrep(i, n - 2, 0) mn[i] = min(mn[i + 1], s[vec[i].se]);

    for (int u, v; q; q--){
        cin >> u >> v;
        int l = pos[e[u]], r = pos[e[v]], ans = 0, ok = 1;
        int cur = e[u];
        while (cur < s[v]) {
            int nxt = jump(cur, l, r);
//            cerr << cur << ' ' << nxt << endl;
            if (nxt == -1) {
                ok = 0;
                break;
            }
            ans++; cur = vec[nxt].fi;
        }
        if (u > v || !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:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1573 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1573 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -