oj.uz

Submission #599039

# Submission time Handle Problem Language Result Execution time Memory
599039 2022-07-19T09:26:11 Z alextodoran Event Hopping (BOI22_events) C++17
20 / 100
 178 ms 76852 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[20000000];
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 = rmin(l, i);
        if (j == i) {
            j = 0;
            minl[i] = i;
        } else {
            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 Correct 134 ms 74964 KB Output is correct
3 Correct 152 ms 76528 KB Output is correct
4 Correct 167 ms 76436 KB Output is correct
5 Correct 139 ms 74444 KB Output is correct
6 Correct 143 ms 72540 KB Output is correct
7 Correct 141 ms 71888 KB Output is correct
8 Incorrect 114 ms 56224 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 1 ms 852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
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 Incorrect 1 ms 852 KB Output isn't correct
8 Halted 0 ms 0 KB -

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 Incorrect 1 ms 852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 74852 KB Output is correct
2 Correct 148 ms 76488 KB Output is correct
3 Correct 164 ms 76448 KB Output is correct
4 Correct 109 ms 56140 KB Output is correct
5 Correct 147 ms 76852 KB Output is correct
6 Correct 174 ms 76568 KB Output is correct
7 Correct 178 ms 76628 KB Output is correct
8 Correct 166 ms 76648 KB Output is correct
9 Correct 76 ms 34264 KB Output is correct
10 Correct 167 ms 76172 KB Output is correct
11 Correct 150 ms 65612 KB Output is correct
12 Correct 148 ms 76108 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 134 ms 74964 KB Output is correct
3 Correct 152 ms 76528 KB Output is correct
4 Correct 167 ms 76436 KB Output is correct
5 Correct 139 ms 74444 KB Output is correct
6 Correct 143 ms 72540 KB Output is correct
7 Correct 141 ms 71888 KB Output is correct
8 Incorrect 114 ms 56224 KB Output isn't correct
9 Halted 0 ms 0 KB -