oj.uz

Submission #1047295

# Submission time Handle Problem Language Result Execution time Memory
1047295 2024-08-07T11:47:06 Z sofijavelkovska Event Hopping (BOI22_events) C++17
20 / 100
 247 ms 17552 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5, LOG=17;

int n;
int l[MAXN], r[MAXN];

bool rcompare(int x, int y)
{
    if (r[x]<r[y])
        return true;

    return false;
}

bool lcompare(int x, int y)
{
    if (l[x]<l[y])
        return true;

    return false;
}

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);

    int q;
    cin >> n >> q;
    for (int i=0; i<n; i++)
        cin >> l[i] >> r[i];
    int sorted[n];
    for (int i=0; i<n; i++)
        sorted[i]=i;
    sort(sorted, sorted+n, rcompare);
    int ranked[n];
    for (int i=0; i<n; i++)
        ranked[sorted[i]]=i;
    int lsorted[n];
    for (int i=0; i<n; i++)
        lsorted[i]=i;
    sort(lsorted, lsorted+n, lcompare);
    int t=n-1;
    set<int> farthest;
    for (int i=0; i<n; i++)
        farthest.insert(i);
    int blift[n][LOG];
    for (int i=0; i<n; i++)
        for (int j=0; j<LOG; j++)
            blift[i][j]=-1;
    for (int i=n-1; i>=0; i--)
    {
        while (t>=0 && l[lsorted[t]]>r[sorted[i]])
        {
            farthest.erase(ranked[lsorted[t]]);
            t=t-1;
        }
        auto it=farthest.end();
        it--;
        if (*it!=i)
            blift[i][0]=*it;
    }
    for (int j=1; j<LOG; j++)
        for (int i=0; i<n; i++)
            if (blift[i][j-1]!=-1 && blift[blift[i][j-1]][j-1]!=-1)
                blift[i][j]=blift[blift[i][j-1]][j-1];
    /*cout << "blift\n";
    for (int j=0; j<LOG; j++)
    {
        for (int i=0; i<n; i++)
            cout << blift[i][j] << ' ';
        cout << '\n';
    }*/
    /*for (int i=0; i<n; i++)
        cout << ranked[i] << ' ';
    cout << '\n';
    for (int i=0; i<n; i++)
        cout << blift[i][0] << ' ';
    cout << '\n';*/
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        x=ranked[x-1];
        y=ranked[y-1];
        if (x>y)
        {
            cout << "impossible" << '\n';
            continue;
        }
        if (x==y)
        {
            cout << 0 << '\n';
            continue;
        }
        int total=0;
        for (int j=LOG-1; j>=0; j--)
        {
            //cout << "x " << x << '\n';
            if (blift[x][j]!=-1 && blift[x][j]<y)
            {
                x=blift[x][j];
                total=total+(1<<j);
            }
        }
        if (blift[x][0]>=y)
            cout << total+1 << '\n';
        else
            cout << "impossible" << '\n';
    }

    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 14140 KB Output is correct
2 Correct 217 ms 14092 KB Output is correct
3 Correct 247 ms 14136 KB Output is correct
4 Correct 225 ms 14676 KB Output is correct
5 Correct 239 ms 17552 KB Output is correct
6 Correct 214 ms 17420 KB Output is correct
7 Correct 220 ms 17460 KB Output is correct
8 Correct 216 ms 17488 KB Output is correct
9 Correct 76 ms 15524 KB Output is correct
10 Correct 202 ms 16980 KB Output is correct
11 Correct 208 ms 16812 KB Output is correct
12 Correct 206 ms 16952 KB Output is correct

Subtask #6
0 / 30.0

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