oj.uz

Submission #1100997

# Submission time Handle Problem Language Result Execution time Memory
1100997 2024-10-15T08:20:05 Z andrei_iorgulescu Event Hopping (BOI22_events) C++14
20 / 100
 199 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 if (minl[x] <= y)
            cout << "1\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:99:25: warning: unused variable 'ys' [-Wunused-variable]
   99 |             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 137 ms 46232 KB Output is correct
3 Correct 142 ms 46436 KB Output is correct
4 Correct 143 ms 46256 KB Output is correct
5 Correct 143 ms 46772 KB Output is correct
6 Correct 153 ms 47368 KB Output is correct
7 Correct 155 ms 47500 KB Output is correct
8 Incorrect 166 ms 51632 KB Output isn't correct
9 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 23288 KB Output is correct
4 Correct 3 ms 23120 KB Output is correct
5 Correct 3 ms 23296 KB Output is correct
6 Incorrect 3 ms 23120 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 23288 KB Output is correct
4 Correct 3 ms 23120 KB Output is correct
5 Correct 3 ms 23296 KB Output is correct
6 Incorrect 3 ms 23120 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 23288 KB Output is correct
4 Correct 3 ms 23120 KB Output is correct
5 Correct 3 ms 23296 KB Output is correct
6 Incorrect 3 ms 23120 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 145 ms 46308 KB Output is correct
2 Correct 138 ms 46256 KB Output is correct
3 Correct 140 ms 46368 KB Output is correct
4 Correct 159 ms 51528 KB Output is correct
5 Correct 149 ms 46768 KB Output is correct
6 Correct 189 ms 51128 KB Output is correct
7 Correct 199 ms 51120 KB Output is correct
8 Correct 187 ms 51380 KB Output is correct
9 Correct 171 ms 50540 KB Output is correct
10 Correct 176 ms 50868 KB Output is correct
11 Correct 193 ms 50524 KB Output is correct
12 Correct 190 ms 50868 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 137 ms 46232 KB Output is correct
3 Correct 142 ms 46436 KB Output is correct
4 Correct 143 ms 46256 KB Output is correct
5 Correct 143 ms 46772 KB Output is correct
6 Correct 153 ms 47368 KB Output is correct
7 Correct 155 ms 47500 KB Output is correct
8 Incorrect 166 ms 51632 KB Output isn't correct
9 Halted 0 ms 0 KB -