oj.uz

Submission #746293

# Submission time Handle Problem Language Result Execution time Memory
746293 2023-05-22T08:12:46 Z Szil Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 134348 KB 
#include <bits/stdc++.h>
using namespace std;
    
const int MAXN = 100001;
const int K = 30;

struct Event {
    int s, e, idx;

    Event() {
        s = INT_MAX;
        e = INT_MAX;
        idx = 0;
    }

    bool operator<(const Event &x) const {
        return s < x.s;
    }
};

struct Node {
    Node *left, *right;
    Event best; int tl, tr;

    Node(int l_, int r_) : tl(l_), tr(r_), best() {}
    
    void expand() {
        if (left == nullptr) {
            int tm = (tl + tr) / 2;
            left = new Node(tl, tm);
            right = new Node(tm+1, tr);
        }
    }
    
    void upd(int pos, Event val) {
        if (tl == tr) {
            best = min(best, val);
        } else {
            expand();
            int m = (tl + tr) / 2;
            if (pos <= m) {
                left->upd(pos, val);
            } else {
                right->upd(pos, val);
            }
            best = min(left->best, right->best);
        }
    }
    
    Event qry(int l, int r) {
        if (l > r) return Event();
        if (l == tl && r == tr) {
            return best;
        } else {
            expand();
            int m = (tl + tr) / 2;
            return min(left->qry(l, min(r, m)), right->qry(max(l, m+1), r));
        }
    }
};
    
int down[MAXN][K];
    
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;

    Node *root = new Node(1, 2e9);
    vector<Event> events(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> events[i].s >> events[i].e; events[i].idx = i;
        root->upd(events[i].e, events[i]);
    }

    for (int i = 1; i <= n; i++) {
        down[i][0] = root->qry(events[i].s, events[i].e).idx;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < K; j++) {
            down[i][j] = down[down[i][j-1]][j-1];
        }
    }

    while (q--) {
        int a_, b_; cin >> a_ >> b_;
        
        if (a_ == b_) {
            cout << "0\n";
            continue;
        }

        Event a = events[a_], b = events[b_];

        if (a.e > b.e) {
            cout << "impossible\n";
            continue;
        }

        if (b.s <= a.e && a.e <= b.e) {
            cout << "1\n";
            continue;
        }

        int ans = 2;
        for (int i = 0; i < n; i++) {
            int next = down[b.idx][0];
            if (next && a.e < events[next].s) {
                b = events[next];
                ans++;
            }
        }
        /*for (int i = K-1; i >= 0; i--) {
            int next = down[b.idx][i];
            if (next && a.e < events[next].s) {
                cerr << b.s << " " << b.e << " " << events[next].s << " " << events[next].e << " " << i << endl;
                b = events[next];
                ans += (1 << i);
            }
        }*/

        b = events[down[b.idx][0]];

        if (b.s > a.e || a.e > b.e) {
            cout << "impossible\n";
            continue;
        }
        cout << ans << "\n";
    }
    return 0;
}

Compilation message

events.cpp: In constructor 'Node::Node(int, int)':
events.cpp:23:25: warning: 'Node::tr' will be initialized after [-Wreorder]
   23 |     Event best; int tl, tr;
      |                         ^~
events.cpp:23:11: warning:   'Event Node::best' [-Wreorder]
   23 |     Event best; int tl, tr;
      |           ^~~~
events.cpp:25:5: warning:   when initialized here [-Wreorder]
   25 |     Node(int l_, int r_) : tl(l_), tr(r_), best() {}
      |     ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1564 ms 131024 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 5 ms 2132 KB Output is correct
4 Correct 4 ms 2260 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 6 ms 3868 KB Output is correct
8 Correct 6 ms 3924 KB Output is correct
9 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 5 ms 2132 KB Output is correct
4 Correct 4 ms 2260 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 6 ms 3868 KB Output is correct
8 Correct 6 ms 3924 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 5 ms 2132 KB Output is correct
13 Correct 4 ms 2260 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 3 ms 1368 KB Output is correct
16 Correct 5 ms 3924 KB Output is correct
17 Correct 5 ms 3924 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Execution timed out 1575 ms 2880 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 5 ms 2132 KB Output is correct
4 Correct 4 ms 2260 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 3 ms 1364 KB Output is correct
7 Correct 6 ms 3868 KB Output is correct
8 Correct 6 ms 3924 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 5 ms 2132 KB Output is correct
13 Correct 4 ms 2260 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 3 ms 1364 KB Output is correct
16 Correct 9 ms 3924 KB Output is correct
17 Correct 6 ms 3920 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Execution timed out 1529 ms 134348 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 130944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1564 ms 131024 KB Time limit exceeded
3 Halted 0 ms 0 KB -