oj.uz

Submission #599128

# Submission time Handle Problem Language Result Execution time Memory
599128 2022-07-19T10:28:49 Z alextodoran Event Hopping (BOI22_events) C++17
25 / 100
 101 ms 66112 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
 
**/
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N_MAX = 100000;
const int BITS = 17;
 
int N, Q;
struct Event {
    int l, r;
};
bool operator < (const Event &e1, const Event &e2) {
    return make_pair(e1.r, e1.l) < make_pair(e2.r, e2.l);
}
Event events[N_MAX + 2];
int order[N_MAX + 2];
int id[N_MAX + 2];
 
struct SegTree {
    int left, right;
    int sum;
};
 
SegTree trees[N_MAX * 20];
int curr;
 
void build (int node, int l, int r) {
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    trees[node].left = ++curr;
    trees[node].right = ++curr;
    build(trees[node].left, l, mid);
    build(trees[node].right, mid + 1, r);
}
void build (int node) {
    build(node, 1, N);
}
 
int update (int node, int l, int r, int upos, int uval) {
    trees[++curr] = trees[node]; node = curr;
    if (l == r) {
        trees[node].sum += uval;
        return node;
    }
    int mid = (l + r) / 2;
    if (upos <= mid) {
        trees[node].left = update(trees[node].left, l, mid, upos, uval);
    } else {
        trees[node].right = update(trees[node].right, mid + 1, r, upos, uval);
    }
    trees[node].sum = trees[trees[node].left].sum + trees[trees[node].right].sum;
    return node;
}
int update (int node, int upos, int uval) {
    if (!(1 <= upos && upos <= N)) {
        return node;
    }
    return update(node, 1, N, upos, uval);
}
 
int query (int node, int l, int r, int qpos) {
    if (qpos <= l) {
        return trees[node].sum;
    }
    int mid = (l + r) / 2;
    if (qpos <= mid) {
        return query(trees[node].left, l, mid, qpos) + trees[trees[node].right].sum;
    } else {
        return query(trees[node].right, mid + 1, r, qpos);
    }
}
int query (int node, int qpos) {
    return query(node, 1, N, qpos);
}
 
int root[N_MAX + 2];
 
int rm[N_MAX + 2][BITS];
int lg2[N_MAX + 2];
void precalc () {
    for (int i = 1; i <= N; i++) {
        rm[i][0] = i;
        lg2[i] = lg2[i - 1];
        if ((1 << (lg2[i] + 1)) <= i) {
            lg2[i]++;
        }
    }
    for (int bit = 1; bit < BITS; bit++) {
        for (int i = 1; i + (1 << bit) - 1 <= N; i++) {
            int j = rm[i][bit - 1], k = rm[i + (1 << (bit - 1))][bit - 1];
            rm[i][bit] = (events[j].l <= events[k].l ? j : k);
        }
    }
}
int rmin (int l, int r) {
    int len = r - l + 1;
    int bit = lg2[len];
    int j = rm[l][bit];
    int k = rm[r - (1 << bit) + 1][bit];
    return (events[j].l <= events[k].l ? j : k);
}
 
int minl[N_MAX + 2];
 
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        cin >> events[i].l >> events[i].r;
    }
    iota(order + 1, order + N + 1, 1);
    sort(order + 1, order + N + 1, [&] (const int &i, const int &j) {
        return events[i] < events[j];
    });
    for (int i = 1; i <= N; i++) {
        id[order[i]] = i;
    }
    sort(events + 1, events + N + 1);
    precalc();
 
    root[0] = ++curr;
    build(root[0]);
    for (int i = 1; i <= N; i++) {
        int l = 1, r = i;
        while (l < r) {
            int mid = (l + r) / 2;
            if (events[i].l <= events[mid].r) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        int j;
        if (l == i) {
            j = 0;
            minl[i] = i;
        } else {
            j = rmin(l, i - 1);
            minl[i] = minl[j];
        }
        root[i] = root[j];
        root[i] = update(root[i], i - 1, +1);
        root[i] = update(root[i], j - 1, -1);
        root[i] = update(root[i], l - 1, +1);
    }
 
    while (Q--) {
        int i, j;
        cin >> i >> j;
        i = id[i]; j = id[j];
        if (i == j) {
            cout << 0 << "\n";
        } else if (events[i].r == events[j].r) {
            cout << 1 << "\n";
        } else if (minl[j] <= i && i < j) {
            cout << query(root[j], i) << "\n";
        } else {
            cout << "impossible\n";
        }
    }
 
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 97 ms 66112 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 30 ms 3760 KB Output is correct
20 Correct 37 ms 3668 KB Output is correct
21 Correct 28 ms 3996 KB Output is correct
22 Correct 25 ms 3736 KB Output is correct
23 Correct 32 ms 3884 KB Output is correct
24 Correct 25 ms 2340 KB Output is correct
25 Correct 30 ms 3528 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Runtime error 101 ms 66076 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 66092 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Runtime error 97 ms 66112 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -