oj.uz

Submission #779528

# Submission time Handle Problem Language Result Execution time Memory
779528 2023-07-11T13:50:36 Z CpDark Event Hopping (BOI22_events) C++14
20 / 100
 216 ms 17452 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 end;
}

bool check(int start, int end, int jumps) {
    int wall = events[start].second;
    int far = jumpK(end, jumps);
    if (events[far].second <= wall && events[start].first>=events[far].first)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 98 ms 17108 KB Output is correct
3 Correct 181 ms 17092 KB Output is correct
4 Correct 216 ms 17108 KB Output is correct
5 Correct 152 ms 17108 KB Output is correct
6 Correct 139 ms 17108 KB Output is correct
7 Correct 132 ms 17176 KB Output is correct
8 Correct 57 ms 17412 KB Output is correct
9 Correct 56 ms 17452 KB Output is correct
10 Correct 125 ms 17320 KB Output is correct
11 Incorrect 87 ms 17388 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 340 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 0 ms 212 KB Output is correct
2 Correct 0 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 340 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 0 ms 212 KB Output is correct
2 Correct 0 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 340 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 94 ms 17108 KB Output is correct
2 Correct 174 ms 17236 KB Output is correct
3 Correct 203 ms 17108 KB Output is correct
4 Correct 57 ms 17452 KB Output is correct
5 Correct 122 ms 17384 KB Output is correct
6 Correct 126 ms 17160 KB Output is correct
7 Correct 114 ms 17116 KB Output is correct
8 Correct 92 ms 17288 KB Output is correct
9 Correct 32 ms 17108 KB Output is correct
10 Correct 124 ms 17108 KB Output is correct
11 Correct 107 ms 17108 KB Output is correct
12 Correct 121 ms 17108 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 98 ms 17108 KB Output is correct
3 Correct 181 ms 17092 KB Output is correct
4 Correct 216 ms 17108 KB Output is correct
5 Correct 152 ms 17108 KB Output is correct
6 Correct 139 ms 17108 KB Output is correct
7 Correct 132 ms 17176 KB Output is correct
8 Correct 57 ms 17412 KB Output is correct
9 Correct 56 ms 17452 KB Output is correct
10 Correct 125 ms 17320 KB Output is correct
11 Incorrect 87 ms 17388 KB Output isn't correct
12 Halted 0 ms 0 KB -