oj.uz

Submission #737046

# Submission time Handle Problem Language Result Execution time Memory
737046 2023-05-06T13:50:45 Z DAleksa Event Hopping (BOI22_events) C++17
30 / 100
 277 ms 31444 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] = 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: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 2 ms 1876 KB Output is correct
2 Correct 195 ms 23896 KB Output is correct
3 Correct 193 ms 26072 KB Output is correct
4 Correct 239 ms 26088 KB Output is correct
5 Correct 206 ms 26624 KB Output is correct
6 Correct 223 ms 27096 KB Output is correct
7 Correct 199 ms 27220 KB Output is correct
8 Correct 199 ms 31348 KB Output is correct
9 Correct 190 ms 31444 KB Output is correct
10 Correct 215 ms 26392 KB Output is correct
11 Correct 215 ms 28380 KB Output is correct
12 Correct 113 ms 25824 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 2 ms 1876 KB Output is correct
3 Correct 2 ms 2084 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 2 ms 1876 KB Output is correct
3 Correct 2 ms 2084 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 2 ms 1876 KB Output is correct
3 Correct 2 ms 2084 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 180 ms 23776 KB Output is correct
2 Correct 197 ms 26088 KB Output is correct
3 Correct 277 ms 26072 KB Output is correct
4 Correct 201 ms 31300 KB Output is correct
5 Correct 198 ms 26460 KB Output is correct
6 Correct 256 ms 30864 KB Output is correct
7 Correct 231 ms 30844 KB Output is correct
8 Correct 234 ms 30980 KB Output is correct
9 Correct 164 ms 28960 KB Output is correct
10 Correct 249 ms 30516 KB Output is correct
11 Correct 261 ms 30392 KB Output is correct
12 Correct 230 ms 30568 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 195 ms 23896 KB Output is correct
3 Correct 193 ms 26072 KB Output is correct
4 Correct 239 ms 26088 KB Output is correct
5 Correct 206 ms 26624 KB Output is correct
6 Correct 223 ms 27096 KB Output is correct
7 Correct 199 ms 27220 KB Output is correct
8 Correct 199 ms 31348 KB Output is correct
9 Correct 190 ms 31444 KB Output is correct
10 Correct 215 ms 26392 KB Output is correct
11 Correct 215 ms 28380 KB Output is correct
12 Correct 113 ms 25824 KB Output is correct
13 Correct 1 ms 1876 KB Output is correct
14 Correct 2 ms 1876 KB Output is correct
15 Correct 2 ms 2084 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 -