oj.uz

Submission #738054

# Submission time Handle Problem Language Result Execution time Memory
738054 2023-05-08T06:36:27 Z DAleksa Event Hopping (BOI22_events) C++17
30 / 100
 295 ms 51868 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

struct seg {
    int L;
    int R;
};

const int N = 1e5 + 10, LOG = 18;
int n, q;
map<int, int> m;
seg a[N];
int sparse[N][LOG];
int st[16 * N];
int L[4 * N];

void build(int index, int l, int r) {
    if(l > r) return;
    if(l == r) {
        st[index] = L[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * index + 1, l, mid);
    build(2 * index + 2, mid + 1, r);
    st[index] = min(st[2 * index + 1], st[2 * index + 2]);
}

int get(int index, int l, int r, int L, int R) {
    if(l > r || r < L || R < l) return 1000000000;
    if(L <= l && r <= R) return st[index];
    int mid = (l + r) / 2;
    return min(get(2 * index + 1, l, mid, L, R), get(2 * index + 2, mid + 1, r, L, R));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    vector<int> compress;
    for(int i = 0; i < n; i++) {
        cin >> a[i].L >> a[i].R;
        compress.push_back(a[i].L);
        compress.push_back(a[i].R);
    }
    sort(compress.begin(), compress.end());
    for(int i = 0; i < n; i++) {
        int oldL = a[i].L, oldR = a[i].R;
        a[i].L = lower_bound(compress.begin(), compress.end(), a[i].L) - compress.begin();
        a[i].R = lower_bound(compress.begin(), compress.end(), a[i].R) - compress.begin();
        m[oldL] = a[i].L;
        m[oldR] = a[i].R;
    }
    vector<pair<pair<int, bool>, int>> v;
    for(int i = 0; i < n; i++) {
        v.push_back({{a[i].L, false}, i});
        v.push_back({{a[i].R, true}, i});
    }
    sort(v.begin(), v.end());
    int mx = v[0].second;
    for(int i = 0; i < v.size(); i++) {
        if(v[i].first.second) {
            if(a[v[i].second].R == a[mx].R) sparse[v[i].second][0] = -1;
            else sparse[v[i].second][0] = mx;
        } else {
            if(a[mx].R < a[v[i].second].R) mx = v[i].second;
        }
    }
    for(int j = 1; j < LOG; j++) {
        for(int i = 0; i < n; i++) {
            if(sparse[i][j - 1] == -1) sparse[i][j] = -1;
            else sparse[i][j] = sparse[sparse[i][j - 1]][j - 1];
        }
    }
    for(int i = 0; i < 4 * N; i++) L[i] = 1e9;
    for(int i = 0; i < n; i++) L[a[i].R] = min(L[a[i].R], a[i].L);
    build(0, 0, 4 * n);
    while(q--) {
        int s, e;
        cin >> s >> e;
        s--;
        e--;
        if(s == e) {
            cout << "0\n";
            continue;
        }
        if(a[s].R > a[e].R) {
            cout << "impossible\n";
            continue;
        }
        if(a[s].R >= a[e].L) {
            cout << "1\n";
            continue;
        }
        int res = 0;
        for(int j = LOG - 1; j >= 0; j--) {
            if(sparse[s][j] == -1) continue;
            if(a[sparse[s][j]].R >= a[e].L) continue;
            s = sparse[s][j];
            res += (1 << j);
        }
        int have = get(0, 0, 4 * n, a[e].L, a[e].R);
        if(have <= a[s].R) cout << res + 2 << "\n";
        else cout << "impossible\n";
    }
    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 198 ms 45044 KB Output is correct
3 Correct 207 ms 45024 KB Output is correct
4 Correct 257 ms 44996 KB Output is correct
5 Correct 223 ms 45780 KB Output is correct
6 Correct 234 ms 46436 KB Output is correct
7 Correct 227 ms 46604 KB Output is correct
8 Correct 218 ms 51808 KB Output is correct
9 Correct 216 ms 51868 KB Output is correct
10 Correct 233 ms 45360 KB Output is correct
11 Correct 237 ms 47896 KB Output is correct
12 Correct 132 ms 44716 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3796 KB Output is correct
4 Correct 3 ms 3840 KB Output is correct
5 Incorrect 2 ms 3880 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3796 KB Output is correct
4 Correct 3 ms 3840 KB Output is correct
5 Incorrect 2 ms 3880 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3796 KB Output is correct
4 Correct 3 ms 3840 KB Output is correct
5 Incorrect 2 ms 3880 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 45108 KB Output is correct
2 Correct 236 ms 45112 KB Output is correct
3 Correct 256 ms 44976 KB Output is correct
4 Correct 219 ms 51844 KB Output is correct
5 Correct 235 ms 45416 KB Output is correct
6 Correct 295 ms 51448 KB Output is correct
7 Correct 289 ms 51472 KB Output is correct
8 Correct 273 ms 51508 KB Output is correct
9 Correct 211 ms 49464 KB Output is correct
10 Correct 280 ms 51040 KB Output is correct
11 Correct 276 ms 50828 KB Output is correct
12 Correct 288 ms 51044 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 198 ms 45044 KB Output is correct
3 Correct 207 ms 45024 KB Output is correct
4 Correct 257 ms 44996 KB Output is correct
5 Correct 223 ms 45780 KB Output is correct
6 Correct 234 ms 46436 KB Output is correct
7 Correct 227 ms 46604 KB Output is correct
8 Correct 218 ms 51808 KB Output is correct
9 Correct 216 ms 51868 KB Output is correct
10 Correct 233 ms 45360 KB Output is correct
11 Correct 237 ms 47896 KB Output is correct
12 Correct 132 ms 44716 KB Output is correct
13 Correct 2 ms 3412 KB Output is correct
14 Correct 2 ms 3412 KB Output is correct
15 Correct 3 ms 3796 KB Output is correct
16 Correct 3 ms 3840 KB Output is correct
17 Incorrect 2 ms 3880 KB Output isn't correct
18 Halted 0 ms 0 KB -