oj.uz

답안 #738066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
738066 2023-05-08T06:48:36 Z DAleksa Event Hopping (BOI22_events) C++17
30 / 100
 260 ms 28344 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 && a[s].R <= a[e].R) {
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 174 ms 23028 KB Output is correct
3 Correct 184 ms 22996 KB Output is correct
4 Correct 210 ms 22892 KB Output is correct
5 Correct 201 ms 23468 KB Output is correct
6 Correct 188 ms 23904 KB Output is correct
7 Correct 189 ms 24172 KB Output is correct
8 Correct 194 ms 28104 KB Output is correct
9 Correct 198 ms 28232 KB Output is correct
10 Correct 207 ms 23292 KB Output is correct
11 Correct 211 ms 25296 KB Output is correct
12 Correct 117 ms 23500 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 2004 KB Output is correct
4 Correct 3 ms 2132 KB Output is correct
5 Incorrect 2 ms 2004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 2004 KB Output is correct
4 Correct 3 ms 2132 KB Output is correct
5 Incorrect 2 ms 2004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 2004 KB Output is correct
4 Correct 3 ms 2132 KB Output is correct
5 Incorrect 2 ms 2004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 212 ms 23028 KB Output is correct
2 Correct 199 ms 22916 KB Output is correct
3 Correct 213 ms 22956 KB Output is correct
4 Correct 191 ms 28344 KB Output is correct
5 Correct 203 ms 23360 KB Output is correct
6 Correct 256 ms 27832 KB Output is correct
7 Correct 260 ms 27812 KB Output is correct
8 Correct 230 ms 27920 KB Output is correct
9 Correct 161 ms 27080 KB Output is correct
10 Correct 223 ms 27484 KB Output is correct
11 Correct 235 ms 27328 KB Output is correct
12 Correct 226 ms 27488 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 174 ms 23028 KB Output is correct
3 Correct 184 ms 22996 KB Output is correct
4 Correct 210 ms 22892 KB Output is correct
5 Correct 201 ms 23468 KB Output is correct
6 Correct 188 ms 23904 KB Output is correct
7 Correct 189 ms 24172 KB Output is correct
8 Correct 194 ms 28104 KB Output is correct
9 Correct 198 ms 28232 KB Output is correct
10 Correct 207 ms 23292 KB Output is correct
11 Correct 211 ms 25296 KB Output is correct
12 Correct 117 ms 23500 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 2004 KB Output is correct
16 Correct 3 ms 2132 KB Output is correct
17 Incorrect 2 ms 2004 KB Output isn't correct
18 Halted 0 ms 0 KB -