oj.uz

Submission #738062

# Submission time Handle Problem Language Result Execution time Memory
738062 2023-05-08T06:44:25 Z DAleksa Event Hopping (BOI22_events) C++17
30 / 100
 310 ms 28736 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 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));
}

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());
    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++) {
        assert(a[i].L <= 2 * n);
        assert(a[i].R <= 2 * n);
        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: 'int' and 'std::vector<std::pair<std::pair<int, bool>, 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 1 ms 1876 KB Output is correct
2 Correct 203 ms 23444 KB Output is correct
3 Correct 201 ms 23476 KB Output is correct
4 Correct 216 ms 23460 KB Output is correct
5 Correct 207 ms 24020 KB Output is correct
6 Correct 207 ms 24504 KB Output is correct
7 Correct 196 ms 24660 KB Output is correct
8 Correct 196 ms 28736 KB Output is correct
9 Correct 225 ms 28684 KB Output is correct
10 Correct 216 ms 23808 KB Output is correct
11 Correct 236 ms 25824 KB Output is correct
12 Correct 130 ms 23968 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1860 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 3 ms 2132 KB Output is correct
4 Correct 3 ms 2132 KB Output is correct
5 Incorrect 4 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 2 ms 1860 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 3 ms 2132 KB Output is correct
4 Correct 3 ms 2132 KB Output is correct
5 Incorrect 4 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 2 ms 1860 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 3 ms 2132 KB Output is correct
4 Correct 3 ms 2132 KB Output is correct
5 Incorrect 4 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 203 ms 23532 KB Output is correct
2 Correct 222 ms 23544 KB Output is correct
3 Correct 296 ms 23492 KB Output is correct
4 Correct 199 ms 28676 KB Output is correct
5 Correct 218 ms 23788 KB Output is correct
6 Correct 241 ms 28352 KB Output is correct
7 Correct 271 ms 28388 KB Output is correct
8 Correct 294 ms 28492 KB Output is correct
9 Correct 195 ms 27628 KB Output is correct
10 Correct 269 ms 27912 KB Output is correct
11 Correct 286 ms 27836 KB Output is correct
12 Correct 310 ms 27932 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 203 ms 23444 KB Output is correct
3 Correct 201 ms 23476 KB Output is correct
4 Correct 216 ms 23460 KB Output is correct
5 Correct 207 ms 24020 KB Output is correct
6 Correct 207 ms 24504 KB Output is correct
7 Correct 196 ms 24660 KB Output is correct
8 Correct 196 ms 28736 KB Output is correct
9 Correct 225 ms 28684 KB Output is correct
10 Correct 216 ms 23808 KB Output is correct
11 Correct 236 ms 25824 KB Output is correct
12 Correct 130 ms 23968 KB Output is correct
13 Correct 2 ms 1860 KB Output is correct
14 Correct 2 ms 1876 KB Output is correct
15 Correct 3 ms 2132 KB Output is correct
16 Correct 3 ms 2132 KB Output is correct
17 Incorrect 4 ms 2132 KB Output isn't correct
18 Halted 0 ms 0 KB -