oj.uz

Submission #738065

# Submission time Handle Problem Language Result Execution time Memory
738065 2023-05-08T06:46:39 Z DAleksa Event Hopping (BOI22_events) C++17
30 / 100
 252 ms 31236 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++) {
        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] = 2e9;
    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:62: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]
   62 |     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 183 ms 25924 KB Output is correct
3 Correct 187 ms 25884 KB Output is correct
4 Correct 230 ms 25880 KB Output is correct
5 Correct 211 ms 26524 KB Output is correct
6 Correct 207 ms 26888 KB Output is correct
7 Correct 209 ms 27124 KB Output is correct
8 Correct 209 ms 31188 KB Output is correct
9 Correct 195 ms 31236 KB Output is correct
10 Correct 200 ms 26304 KB Output is correct
11 Correct 205 ms 28220 KB Output is correct
12 Correct 112 ms 25676 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 2132 KB Output is correct
5 Incorrect 2 ms 2140 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 2132 KB Output is correct
5 Incorrect 2 ms 2140 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 2132 KB Output is correct
5 Incorrect 2 ms 2140 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 179 ms 26012 KB Output is correct
2 Correct 218 ms 25928 KB Output is correct
3 Correct 239 ms 25920 KB Output is correct
4 Correct 207 ms 31128 KB Output is correct
5 Correct 195 ms 26284 KB Output is correct
6 Correct 252 ms 30856 KB Output is correct
7 Correct 250 ms 30836 KB Output is correct
8 Correct 223 ms 30908 KB Output is correct
9 Correct 163 ms 28868 KB Output is correct
10 Correct 242 ms 30384 KB Output is correct
11 Correct 239 ms 30180 KB Output is correct
12 Correct 235 ms 30412 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 183 ms 25924 KB Output is correct
3 Correct 187 ms 25884 KB Output is correct
4 Correct 230 ms 25880 KB Output is correct
5 Correct 211 ms 26524 KB Output is correct
6 Correct 207 ms 26888 KB Output is correct
7 Correct 209 ms 27124 KB Output is correct
8 Correct 209 ms 31188 KB Output is correct
9 Correct 195 ms 31236 KB Output is correct
10 Correct 200 ms 26304 KB Output is correct
11 Correct 205 ms 28220 KB Output is correct
12 Correct 112 ms 25676 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 2132 KB Output is correct
17 Incorrect 2 ms 2140 KB Output isn't correct
18 Halted 0 ms 0 KB -