oj.uz

Submission #779508

# Submission time Handle Problem Language Result Execution time Memory
779508 2023-07-11T13:33:39 Z CpDark Event Hopping (BOI22_events) C++14
20 / 100
 282 ms 20608 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const ll inf = 1e18 + 7;

vvp table;
vp events;
vector<pair<int, pii>> endTimes;
int mylog;

int jumpK(int end, int k) {
    for (int i = mylog;i >= 0;i--) {
        if ((k >> i) & 1) {
            end = table[i][end].first;
        }
    }
    return events[end].second;
}

bool check(int start, int end, int jumps) {
    int wall = events[start].second;
    int far = jumpK(end, jumps);
    if (wall >= far)return true;
    return false;
}

int binSearch(int l, int r, int start, int end) {
    if (!check(start, end, r + 1)) return -1;
    
    while (l < r)
    {
        int m = l + (r - l) / 2;
        if (check(start, end, m)) {
            r = m;
        }
        else {
            l = m + 1;
        }
    }
    return l;
}

int query(int start, int end, int n) {
    if (events[start].second > events[end].second)return -1;
    int ans = binSearch(0, n, start, end);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    mylog = ceil(log2(n + 1));
    events.resize(n);
    endTimes.resize(n);
    table.resize(mylog + 1, vp(n));
    
    for (int i = 0;i < n;i++) {
        cin >> events[i].first >> events[i].second;
        endTimes[i] = { events[i].second, {events[i].first, i} };
    }

    sort(endTimes.begin(), endTimes.end());

    for (int i = 0;i < endTimes.size();i++) {
        int index = endTimes[i].second.second;
        int far = lower_bound(endTimes.begin(), endTimes.end(), (pair<int, pii>){ events[index].first, make_pair(-1,-1)}) - endTimes.begin();
        table[0][index] = { endTimes[far].second.second, endTimes[far].first};
    }

    for (int i = 1;i <= mylog;i++) {
        for (int v = 0;v < n;v++) {
            int p = table[i - 1][v].first;
            table[i][v] = table[i - 1][p];
        }
    }

    int s, e;
    for (int i = 0;i < q;i++) {
        cin >> s >> e;
        s--; e--;
        int ans = query(s, e, n);
        if (ans == -1) {
            cout << "impossible\n";
        }
        else {
            cout << ans << '\n';
        }
    }

    return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0;i < endTimes.size();i++) {
      |                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 108 ms 20120 KB Output is correct
3 Correct 186 ms 20112 KB Output is correct
4 Correct 282 ms 20016 KB Output is correct
5 Correct 166 ms 20096 KB Output is correct
6 Correct 143 ms 20188 KB Output is correct
7 Correct 136 ms 20116 KB Output is correct
8 Correct 68 ms 20572 KB Output is correct
9 Correct 60 ms 20608 KB Output is correct
10 Correct 115 ms 20384 KB Output is correct
11 Incorrect 91 ms 20532 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
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 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

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 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 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 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 20108 KB Output is correct
2 Correct 191 ms 20104 KB Output is correct
3 Correct 250 ms 20144 KB Output is correct
4 Correct 61 ms 20512 KB Output is correct
5 Correct 115 ms 20480 KB Output is correct
6 Correct 127 ms 20236 KB Output is correct
7 Correct 122 ms 20228 KB Output is correct
8 Correct 89 ms 20376 KB Output is correct
9 Correct 33 ms 18328 KB Output is correct
10 Correct 134 ms 19872 KB Output is correct
11 Correct 117 ms 19800 KB Output is correct
12 Correct 130 ms 19892 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 108 ms 20120 KB Output is correct
3 Correct 186 ms 20112 KB Output is correct
4 Correct 282 ms 20016 KB Output is correct
5 Correct 166 ms 20096 KB Output is correct
6 Correct 143 ms 20188 KB Output is correct
7 Correct 136 ms 20116 KB Output is correct
8 Correct 68 ms 20572 KB Output is correct
9 Correct 60 ms 20608 KB Output is correct
10 Correct 115 ms 20384 KB Output is correct
11 Incorrect 91 ms 20532 KB Output isn't correct
12 Halted 0 ms 0 KB -