oj.uz

Submission #738059

# Submission time Handle Problem Language Result Execution time Memory
738059 2023-05-08T06:43:30 Z DAleksa Event Hopping (BOI22_events) C++17
30 / 100
 268 ms 28720 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 182 ms 23600 KB Output is correct
3 Correct 191 ms 23552 KB Output is correct
4 Correct 234 ms 23488 KB Output is correct
5 Correct 195 ms 24056 KB Output is correct
6 Correct 194 ms 24544 KB Output is correct
7 Correct 213 ms 24696 KB Output is correct
8 Correct 191 ms 28720 KB Output is correct
9 Correct 208 ms 28708 KB Output is correct
10 Correct 251 ms 23856 KB Output is correct
11 Correct 221 ms 25804 KB Output is correct
12 Correct 119 ms 23956 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 2 ms 2132 KB Output is correct
4 Correct 2 ms 2028 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 2 ms 2132 KB Output is correct
4 Correct 2 ms 2028 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 2 ms 2132 KB Output is correct
4 Correct 2 ms 2028 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 186 ms 23520 KB Output is correct
2 Correct 203 ms 23512 KB Output is correct
3 Correct 215 ms 23512 KB Output is correct
4 Correct 215 ms 28700 KB Output is correct
5 Correct 218 ms 23944 KB Output is correct
6 Correct 245 ms 28428 KB Output is correct
7 Correct 268 ms 28308 KB Output is correct
8 Correct 234 ms 28424 KB Output is correct
9 Correct 183 ms 27524 KB Output is correct
10 Correct 254 ms 28000 KB Output is correct
11 Correct 245 ms 27840 KB Output is correct
12 Correct 239 ms 27916 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 182 ms 23600 KB Output is correct
3 Correct 191 ms 23552 KB Output is correct
4 Correct 234 ms 23488 KB Output is correct
5 Correct 195 ms 24056 KB Output is correct
6 Correct 194 ms 24544 KB Output is correct
7 Correct 213 ms 24696 KB Output is correct
8 Correct 191 ms 28720 KB Output is correct
9 Correct 208 ms 28708 KB Output is correct
10 Correct 251 ms 23856 KB Output is correct
11 Correct 221 ms 25804 KB Output is correct
12 Correct 119 ms 23956 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 1 ms 1876 KB Output is correct
15 Correct 2 ms 2132 KB Output is correct
16 Correct 2 ms 2028 KB Output is correct
17 Incorrect 2 ms 2132 KB Output isn't correct
18 Halted 0 ms 0 KB -