oj.uz

Submission #579700

# Submission time Handle Problem Language Result Execution time Memory
579700 2022-06-19T16:13:36 Z Elias Event Hopping (BOI22_events) C++17
0 / 100
 312 ms 33456 KB 
#include <bits/stdc++.h>

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#endif

using namespace std;

#define int int64_t

template <class T>
istream &operator>>(istream &in, vector<T> &v)
{
    for (T &x : v)
        in >> x;
    return in;
}

struct Range
{
    int s, e;
};

struct T
{
    int s, i;

    bool operator<(T other) const
    {
        return pair<int, int>(s, i) < pair<int, int>(other.s, other.i);
    }
};

int n, q;

vector<Range> ranges;

vector<T> b;
T neutral = {LLONG_MAX / 2, -1};

T update(int l, int r, int i, int k, T x)
{
    if (k >= r || k < l)
        return b[i];
    if (l + 1 == r)
        return b[i] = min(b[i], x);
    int m = (l + r) / 2;
    return b[i] = min(update(l, m, i * 2 + 1, k, x), update(m, r, i * 2 + 2, k, x));
}

T query(int l, int r, int i, int ql, int qr)
{
    if (l >= qr || ql >= r)
        return neutral;
    if (l >= ql && r <= qr)
        return b[i];
    int m = (l + r) / 2;
    return min(query(l, m, i * 2 + 1, ql, qr), query(m, r, i * 2 + 2, ql, qr));
}

signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> q;

    ranges = vector<Range>(n);

    vector<int> vals;

    for (int i = 0; i < n; i++)
    {
        cin >> ranges[i].s >> ranges[i].e;
        vals.push_back(ranges[i].s);
        vals.push_back(ranges[i].e);
    }

    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    b = vector<T>(vals.size() * 4, neutral);

    for (int i = 0; i < n; i++)
    {
        ranges[i].s = lower_bound(vals.begin(), vals.end(), ranges[i].s) - vals.begin();
        ranges[i].e = lower_bound(vals.begin(), vals.end(), ranges[i].e) - vals.begin();
    }

    for (int i = 0; i < n; i++)
        update(0, vals.size(), 0, ranges[i].e, {ranges[i].s, i});

    vector<vector<int>> prev(20, vector<int>(n, -1));

    for (int i = 0; i < n; i++)
    {
        prev[0][i] = query(0, vals.size(), 0, ranges[i].s, ranges[i].e + 1).i;
        if (prev[0][i] == i)
            prev[0][i] = -1;
    }

    for (int k = 1; k < 20; k++)
        for (int i = 0; i < n; i++)
        {
            if (prev[k - 1][i] != -1)
                prev[k][i] = prev[k - 1][prev[k - 1][i]];
        }

    while (q--)
    {
        int s, e;
        cin >> s >> e;

        s--, e--;

        if (s == e)
        {
            cout << "0\n";
            continue;
        }

        int cost = 0;

        for (int k = 19; k >= 0; k--)
        {
            if (prev[k][e] != -1 && ranges[prev[k][e]].s > ranges[s].e)
                e = prev[k][e], cost += pow(2, k);
        }

        while (e != -1 && ranges[e].s > ranges[s].e)
        {
            e = prev[0][e]; // move to reachable one
            cost++;
        }

        if (e != -1 && ranges[e].s <= ranges[s].e)
        {
            cout << cost + (e != s) << "\n";
        }
        else
        {
            cout << "impossible\n";
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 190 ms 26640 KB Output is correct
3 Correct 221 ms 26768 KB Output is correct
4 Correct 312 ms 26616 KB Output is correct
5 Correct 245 ms 27428 KB Output is correct
6 Correct 218 ms 27976 KB Output is correct
7 Correct 218 ms 28132 KB Output is correct
8 Correct 185 ms 33456 KB Output is correct
9 Correct 188 ms 33440 KB Output is correct
10 Incorrect 267 ms 26616 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 26688 KB Output is correct
2 Correct 210 ms 26672 KB Output is correct
3 Correct 286 ms 26640 KB Output is correct
4 Correct 177 ms 33448 KB Output is correct
5 Incorrect 256 ms 26664 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 190 ms 26640 KB Output is correct
3 Correct 221 ms 26768 KB Output is correct
4 Correct 312 ms 26616 KB Output is correct
5 Correct 245 ms 27428 KB Output is correct
6 Correct 218 ms 27976 KB Output is correct
7 Correct 218 ms 28132 KB Output is correct
8 Correct 185 ms 33456 KB Output is correct
9 Correct 188 ms 33440 KB Output is correct
10 Incorrect 267 ms 26616 KB Output isn't correct
11 Halted 0 ms 0 KB -