oj.uz

Submission #1100996

# Submission time Handle Problem Language Result Execution time Memory
1100996 2024-10-15T08:17:45 Z andrei_iorgulescu Event Hopping (BOI22_events) C++14
20 / 100
 201 ms 51632 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 - 1).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 14672 KB Output is correct
2 Correct 135 ms 46300 KB Output is correct
3 Correct 140 ms 46256 KB Output is correct
4 Correct 144 ms 46284 KB Output is correct
5 Correct 143 ms 46768 KB Output is correct
6 Correct 144 ms 47196 KB Output is correct
7 Correct 144 ms 47536 KB Output is correct
8 Correct 160 ms 51632 KB Output is correct
9 Correct 165 ms 51552 KB Output is correct
10 Correct 161 ms 46768 KB Output is correct
11 Incorrect 157 ms 48560 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 12624 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 3 ms 23296 KB Output is correct
4 Correct 3 ms 23120 KB Output is correct
5 Correct 3 ms 23116 KB Output is correct
6 Incorrect 3 ms 23288 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 12624 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 3 ms 23296 KB Output is correct
4 Correct 3 ms 23120 KB Output is correct
5 Correct 3 ms 23116 KB Output is correct
6 Incorrect 3 ms 23288 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 12624 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 3 ms 23296 KB Output is correct
4 Correct 3 ms 23120 KB Output is correct
5 Correct 3 ms 23116 KB Output is correct
6 Incorrect 3 ms 23288 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 46412 KB Output is correct
2 Correct 135 ms 46384 KB Output is correct
3 Correct 154 ms 46256 KB Output is correct
4 Correct 165 ms 51632 KB Output is correct
5 Correct 153 ms 46768 KB Output is correct
6 Correct 191 ms 51300 KB Output is correct
7 Correct 191 ms 51292 KB Output is correct
8 Correct 201 ms 51380 KB Output is correct
9 Correct 166 ms 50488 KB Output is correct
10 Correct 179 ms 50788 KB Output is correct
11 Correct 195 ms 50632 KB Output is correct
12 Correct 175 ms 50852 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 135 ms 46300 KB Output is correct
3 Correct 140 ms 46256 KB Output is correct
4 Correct 144 ms 46284 KB Output is correct
5 Correct 143 ms 46768 KB Output is correct
6 Correct 144 ms 47196 KB Output is correct
7 Correct 144 ms 47536 KB Output is correct
8 Correct 160 ms 51632 KB Output is correct
9 Correct 165 ms 51552 KB Output is correct
10 Correct 161 ms 46768 KB Output is correct
11 Incorrect 157 ms 48560 KB Output isn't correct
12 Halted 0 ms 0 KB -