oj.uz

Submission #653874

# Submission time Handle Problem Language Result Execution time Memory
653874 2022-10-28T17:20:30 Z couplefire Event Hopping (BOI22_events) C++17
30 / 100
 290 ms 28448 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1<<17;
const int INF = 0x3f3f3f3f;

int n, q;
pair<int, int> segs[N];
map<int, int> mp;
vector<int> stuff;
int bruh[N<<1];
int tree[N<<2];
int to[N][20];

void upd(int pos, int val, int tl = 0, int tr = (N<<1)-1, int v = 1) {
    if (tr < pos || tl > pos) {
        return;
    }
    if (tl == tr) {
        tree[v] = min(tree[v], val);
        return;
    }
    int tm = (tl+tr)>>1;
    upd(pos, val, tl, tm, v<<1);
    upd(pos, val, tm+1, tr, v<<1|1);
    tree[v] = min(tree[v<<1], tree[v<<1|1]);
}

int query(int l, int r, int tl = 0, int tr = (N<<1)-1, int v = 1) {
    if (tr < l || tl > r) {
        return INF;
    }
    if (l <= tl && tr <= r) {
        return tree[v];
    }
    int tm = (tl+tr)>>1;
    return min(query(l, r, tl, tm, v<<1), query(l, r, tm+1, tr, v<<1|1));
}

int main() {
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(tree, INF, sizeof tree);
    memset(to, -1, sizeof to);
    memset(bruh, -1, sizeof bruh);

    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> segs[i].first >> segs[i].second;
        stuff.push_back(segs[i].first);
        stuff.push_back(segs[i].second);
    }
    sort(stuff.begin(), stuff.end());
    stuff.erase(unique(stuff.begin(), stuff.end()), stuff.end());
    for (int i = 0; i < stuff.size(); ++i) {
        mp[stuff[i]] = i;
    }
    for (int i = 0; i < n; ++i) {
        segs[i].first = mp[segs[i].first];
        segs[i].second = mp[segs[i].second];
        upd(segs[i].second, segs[i].first);
        if (bruh[segs[i].first] == -1 || segs[bruh[segs[i].first]].second > segs[i].second) {
            bruh[segs[i].first] = i;
        }
    }
    for (int i = 0; i < n; ++i) {
        int val = query(segs[i].first, segs[i].second);
        if (val < segs[i].first) {
            to[i][0] = bruh[val];
        }
    }
    for (int i = 1; i < 20; ++i) {
        for (int j = 0; j < n; ++j) {
            if (to[j][i-1] != -1) {
                to[j][i] = to[to[j][i-1]][i-1];
            }
        }
    }
    while (q--) {
        int s, e;
        cin >> s >> e;
        --s, --e;
        if (s == e) {
            cout << 0 << '\n';
            continue;
        }
        if (segs[s].second > segs[e].second) {
            cout << "impossible" << '\n';
            continue;
        }
        if (segs[s].second >= segs[e].first) {
            cout << 1 << '\n';
            continue;
        }
        int ans = 0, cur = e;
        for (int i = 19; i >= 0; --i) {
            if (to[cur][i] != -1 && segs[s].second < segs[to[cur][i]].first) {
                ans += (1<<i);
                cur = to[cur][i];
            }
        }
        if (to[cur][0] != -1) {
            cout << ans+2 << '\n';
        } else {
            cout << "impossible" << '\n';
        }
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < stuff.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13652 KB Output is correct
2 Correct 175 ms 22664 KB Output is correct
3 Correct 203 ms 23204 KB Output is correct
4 Correct 264 ms 23208 KB Output is correct
5 Correct 212 ms 23636 KB Output is correct
6 Correct 220 ms 24120 KB Output is correct
7 Correct 203 ms 24312 KB Output is correct
8 Correct 219 ms 28360 KB Output is correct
9 Correct 224 ms 28276 KB Output is correct
10 Correct 217 ms 23448 KB Output is correct
11 Correct 230 ms 25280 KB Output is correct
12 Correct 119 ms 23072 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13664 KB Output is correct
2 Correct 6 ms 13652 KB Output is correct
3 Correct 7 ms 13672 KB Output is correct
4 Correct 7 ms 13780 KB Output is correct
5 Correct 7 ms 13652 KB Output is correct
6 Incorrect 7 ms 13688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13664 KB Output is correct
2 Correct 6 ms 13652 KB Output is correct
3 Correct 7 ms 13672 KB Output is correct
4 Correct 7 ms 13780 KB Output is correct
5 Correct 7 ms 13652 KB Output is correct
6 Incorrect 7 ms 13688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13664 KB Output is correct
2 Correct 6 ms 13652 KB Output is correct
3 Correct 7 ms 13672 KB Output is correct
4 Correct 7 ms 13780 KB Output is correct
5 Correct 7 ms 13652 KB Output is correct
6 Incorrect 7 ms 13688 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 22520 KB Output is correct
2 Correct 255 ms 23376 KB Output is correct
3 Correct 243 ms 23292 KB Output is correct
4 Correct 246 ms 28448 KB Output is correct
5 Correct 214 ms 23728 KB Output is correct
6 Correct 248 ms 28176 KB Output is correct
7 Correct 256 ms 27392 KB Output is correct
8 Correct 282 ms 27440 KB Output is correct
9 Correct 215 ms 26480 KB Output is correct
10 Correct 275 ms 27044 KB Output is correct
11 Correct 290 ms 26952 KB Output is correct
12 Correct 287 ms 26948 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13652 KB Output is correct
2 Correct 175 ms 22664 KB Output is correct
3 Correct 203 ms 23204 KB Output is correct
4 Correct 264 ms 23208 KB Output is correct
5 Correct 212 ms 23636 KB Output is correct
6 Correct 220 ms 24120 KB Output is correct
7 Correct 203 ms 24312 KB Output is correct
8 Correct 219 ms 28360 KB Output is correct
9 Correct 224 ms 28276 KB Output is correct
10 Correct 217 ms 23448 KB Output is correct
11 Correct 230 ms 25280 KB Output is correct
12 Correct 119 ms 23072 KB Output is correct
13 Correct 7 ms 13664 KB Output is correct
14 Correct 6 ms 13652 KB Output is correct
15 Correct 7 ms 13672 KB Output is correct
16 Correct 7 ms 13780 KB Output is correct
17 Correct 7 ms 13652 KB Output is correct
18 Incorrect 7 ms 13688 KB Output isn't correct
19 Halted 0 ms 0 KB -