oj.uz

Submission #1100995

# Submission time Handle Problem Language Result Execution time Memory
1100995 2024-10-15T08:13:24 Z andrei_iorgulescu Event Hopping (BOI22_events) C++14
20 / 100
 198 ms 54744 KB 
#include <bits/stdc++.h>

using namespace std;

int n, q;
int s[100005], e[100005];
int minl[200005];
int f[200005];

void normalize()
{
    vector<int> pp;
    map<int, int> norma;
    for (int i = 1; i <= n; i++)
        pp.push_back(s[i]), pp.push_back(e[i]);
    sort(pp.begin(), pp.end());
    int poo = 0;
    for (auto it : pp)
        if (!norma[it])
            norma[it] = ++poo;
    for (int i = 1; i <= n; i++)
        s[i] = norma[s[i]], e[i] = norma[e[i]];
    for (int i = 1; i <= 2 * n; i++)
        minl[i] = i;
    for (int i = 1; i <= n; i++)
        minl[e[i]] = min(minl[e[i]], s[i]);
}

pair<int, int> aint[800005];///val, pos

void build(int nod, int l, int r)
{
    if (l == r)
    {
        aint[nod] = {minl[l], l};
        return;
    }
    int mij = (l + r) / 2;
    build(2 * nod, l, mij);
    build(2 * nod + 1, mij + 1, r);
    aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
}

pair<int, int> query(int nod, int l, int r, int st, int dr)
{
    if (r < st or dr < l)
        return {1e9, 0};
    else if (st <= l and r <= dr)
        return aint[nod];
    int mij = (l + r) / 2;
    return min(query(2 * nod, l, mij, st, dr), query(2 * nod + 1, mij + 1, r, st, dr));
}

int lg[200005];
int bl[20][200005], bl1[20][200005];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> s[i] >> e[i];
    normalize();
    build(1, 1, 2 * n);
    for (int i = 1; i <= 2 * n; i++)
        f[i] = query(1, 1, 2 * n, minl[i], i).second;
    for (int i = 2; i <= 2 * n; i++)
        lg[i] = 1 + lg[i / 2];
    for (int i = 1; i <= 2 * n; i++)
        bl[0][i] = f[i];
    for (int j = 1; j <= lg[2 * n]; j++)
        for (int i = 1; i <= 2 * n; i++)
            bl[j][i] = bl[j - 1][bl[j - 1][i]];
    for (int i = 1; i <= 2 * n; i++)
        bl1[0][i] = i;
    for (int j = 1; j <= lg[2 * n]; j++)
        for (int i = 1; i <= 2 * n; i++)
            bl1[j][i] = bl[j - 1][bl1[j - 1][i]];
    for (int i = 1; i <= q; i++)
    {
        int x, y;
        cin >> x >> y;
        int xx = x, yy = y;
        if (x == y)
        {
            cout << "0\n";
            continue;
        }
        x = e[x], y = e[y];
        swap(x, y);
        if (x < y)
            cout << "impossible\n";
        else
        {
            int xs = x, ys = y;
            int ans = 1;
            for (int pas = lg[2 * n]; pas >= 0; pas--)
            {
                if (minl[bl1[pas][x]] > y)
                    ans += (1 << pas), x = bl[pas][x];
            }
            if (minl[x] > y)
                cout << "impossible\n";
            else
            {
                if (s[yy] == minl[xs])
                    cout << ans << '\n';
                else
                {
                    ///maybe ans + 1?
                    x = query(1, 1, 2 * n, s[yy], xs).second;
                    int ans2 = ans;
                    ans = 2;
                    for (int pas = lg[2 * n]; pas >= 0; pas--)
                    {
                        if (minl[bl1[pas][x]] > y)
                            ans += (1 << pas), x = bl[pas][x];
                    }
                    if (minl[x] > y)
                        cout << ans2 + 1 << '\n';
                    else
                        cout << min(ans2 + 1, ans) << '\n';
                }
            }
        }
    }
    return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:97:25: warning: unused variable 'ys' [-Wunused-variable]
   97 |             int xs = x, ys = y;
      |                         ^~
events.cpp:85:13: warning: unused variable 'xx' [-Wunused-variable]
   85 |         int xx = x, yy = y;
      |             ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14812 KB Output is correct
2 Correct 139 ms 49496 KB Output is correct
3 Correct 146 ms 49336 KB Output is correct
4 Correct 148 ms 49336 KB Output is correct
5 Correct 151 ms 50036 KB Output is correct
6 Correct 148 ms 50356 KB Output is correct
7 Correct 155 ms 50620 KB Output is correct
8 Correct 168 ms 54744 KB Output is correct
9 Correct 168 ms 54708 KB Output is correct
10 Correct 157 ms 49844 KB Output is correct
11 Incorrect 161 ms 51636 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12764 KB Output is correct
2 Correct 2 ms 14676 KB Output is correct
3 Correct 3 ms 23288 KB Output is correct
4 Correct 4 ms 23380 KB Output is correct
5 Correct 3 ms 23124 KB Output is correct
6 Incorrect 3 ms 23124 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12764 KB Output is correct
2 Correct 2 ms 14676 KB Output is correct
3 Correct 3 ms 23288 KB Output is correct
4 Correct 4 ms 23380 KB Output is correct
5 Correct 3 ms 23124 KB Output is correct
6 Incorrect 3 ms 23124 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12764 KB Output is correct
2 Correct 2 ms 14676 KB Output is correct
3 Correct 3 ms 23288 KB Output is correct
4 Correct 4 ms 23380 KB Output is correct
5 Correct 3 ms 23124 KB Output is correct
6 Incorrect 3 ms 23124 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 137 ms 49728 KB Output is correct
2 Correct 142 ms 49344 KB Output is correct
3 Correct 145 ms 49332 KB Output is correct
4 Correct 163 ms 54740 KB Output is correct
5 Correct 148 ms 49876 KB Output is correct
6 Correct 194 ms 54320 KB Output is correct
7 Correct 194 ms 54196 KB Output is correct
8 Correct 198 ms 54452 KB Output is correct
9 Correct 166 ms 52404 KB Output is correct
10 Correct 179 ms 54020 KB Output is correct
11 Correct 188 ms 53872 KB Output is correct
12 Correct 197 ms 53952 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14812 KB Output is correct
2 Correct 139 ms 49496 KB Output is correct
3 Correct 146 ms 49336 KB Output is correct
4 Correct 148 ms 49336 KB Output is correct
5 Correct 151 ms 50036 KB Output is correct
6 Correct 148 ms 50356 KB Output is correct
7 Correct 155 ms 50620 KB Output is correct
8 Correct 168 ms 54744 KB Output is correct
9 Correct 168 ms 54708 KB Output is correct
10 Correct 157 ms 49844 KB Output is correct
11 Incorrect 161 ms 51636 KB Output isn't correct
12 Halted 0 ms 0 KB -