oj.uz

Submission #738112

# Submission time Handle Problem Language Result Execution time Memory
738112 2023-05-08T07:36:51 Z DAleksa Event Hopping (BOI22_events) C++17
30 / 100
 260 ms 31300 KB 
#include <bits/stdc++.h>

using namespace std;

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 1e9;
    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));
}

int 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());
    compress.erase(unique(compress.begin(), compress.end()), 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:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, bool>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 195 ms 26080 KB Output is correct
3 Correct 220 ms 26076 KB Output is correct
4 Correct 238 ms 26048 KB Output is correct
5 Correct 201 ms 26636 KB Output is correct
6 Correct 204 ms 27108 KB Output is correct
7 Correct 209 ms 27264 KB Output is correct
8 Correct 215 ms 31292 KB Output is correct
9 Correct 193 ms 31296 KB Output is correct
10 Correct 208 ms 26468 KB Output is correct
11 Correct 217 ms 28324 KB Output is correct
12 Correct 108 ms 25816 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 3 ms 2132 KB Output is correct
4 Correct 2 ms 2132 KB Output is correct
5 Incorrect 2 ms 2132 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 192 ms 26084 KB Output is correct
2 Correct 205 ms 26056 KB Output is correct
3 Correct 243 ms 26072 KB Output is correct
4 Correct 224 ms 31300 KB Output is correct
5 Correct 219 ms 26452 KB Output is correct
6 Correct 249 ms 30904 KB Output is correct
7 Correct 260 ms 30908 KB Output is correct
8 Correct 231 ms 31004 KB Output is correct
9 Correct 194 ms 28944 KB Output is correct
10 Correct 250 ms 30588 KB Output is correct
11 Correct 253 ms 30316 KB Output is correct
12 Correct 240 ms 30532 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 195 ms 26080 KB Output is correct
3 Correct 220 ms 26076 KB Output is correct
4 Correct 238 ms 26048 KB Output is correct
5 Correct 201 ms 26636 KB Output is correct
6 Correct 204 ms 27108 KB Output is correct
7 Correct 209 ms 27264 KB Output is correct
8 Correct 215 ms 31292 KB Output is correct
9 Correct 193 ms 31296 KB Output is correct
10 Correct 208 ms 26468 KB Output is correct
11 Correct 217 ms 28324 KB Output is correct
12 Correct 108 ms 25816 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 1 ms 1876 KB Output is correct
15 Correct 3 ms 2132 KB Output is correct
16 Correct 2 ms 2132 KB Output is correct
17 Incorrect 2 ms 2132 KB Output isn't correct
18 Halted 0 ms 0 KB -