oj.uz

Submission #1047432

# Submission time Handle Problem Language Result Execution time Memory
1047432 2024-08-07T12:57:30 Z sofijavelkovska Event Hopping (BOI22_events) C++17
25 / 100
 1500 ms 19028 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=(1<<18), INF=1e9;

int n;
int l[MAXN], r[MAXN];
//int tree[2*MAXN-1];

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

    return r[x]<r[y];
}

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

    return false;
}

/*int find(int x, int l, int r, int lt, int rt)
{
    if (l>=rt || r<=lt)
        return INF;
    if (l>=lt && r<=rt)
        return tree[x];

    return min(find(2*x+1, l, (l+r)/2, lt, rt), find(2*x+2, (l+r)/2, r, lt, rt));
}

void update(int x, int l, int r, int index, int value)
{
    if (l>index || r<=index)
        return;
    if (r-l==1)
    {
        tree[x]=min(tree[x], value);
        return;
    }
    update(2*x+1, l, (l+r)/2, index, value);
    update(2*x+2, (l+r)/2, r, index, value);
    tree[x]=min(tree[2*x+1], tree[2*x+2]);

    return;
}*/

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;
    map<int, int> compress;
    for (int i=0; i<n; i++)
    {
        compress[l[i]]=0;
        compress[r[i]]=0;
    }
    int counter=0;
    for (auto x : compress)
    {
        compress[x.first]=counter;
        counter=counter+1;
    }
    int lsorted[n];
    for (int i=0; i<n; i++)
        lsorted[i]=i;
    sort(lsorted, lsorted+n, lcompare);
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        x=x-1;
        y=y-1;
        if (x==y)
        {
            cout << 0 << '\n';
            continue;
        }
        if (r[x]>r[y])
        {
            cout << "impossible" << '\n';
            continue;
        }
        if (r[x]==r[y])
        {
            cout << 1 << '\n';
            continue;
        }
        //for (int i=0; i<2*MAXN-1; i++)
           // tree[i]=INF;
        int dp[n];
        dp[ranked[y]]=0;
        multiset<int> best;
        best.insert(0);
        //update(0, 0, MAXN, compress[l[y]], 0);
        int t=n-1;
        for (int i=ranked[y]-1; i>=0; i--)
        {
            while (t>=0 && l[lsorted[t]]>r[sorted[i]])
            {
                if (ranked[lsorted[t]]<=ranked[y] && dp[ranked[lsorted[t]]]!=INF)
                    best.erase(best.find(dp[ranked[lsorted[t]]]));
                t=t-1;
            }
            dp[i]=INF;
            if (!best.empty())
                dp[i]=*best.begin()+1;
            if (dp[i]!=INF)
                best.insert(dp[i]);
            //cout << "l r " << l[sorted[i]] << ' ' << r[sorted[i]] << '\n';
            //cout << "find " << find(0, 0, MAXN, 0, compress[r[sorted[i]]]+1) << '\n';
            //update(0, 0, MAXN, compress[l[sorted[i]]], dp[i]);
            //cout << "dp " << dp[i] << '\n';
        }
        if (dp[ranked[x]]!=INF)
            cout << dp[ranked[x]] << '\n';
        else
            cout << "impossible" << '\n';
    }

    return 0;
}



/*#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];
    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--)
        {
            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 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1545 ms 7344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 536 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 4 ms 428 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 536 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 4 ms 428 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 3 ms 348 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Execution timed out 1598 ms 1048 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 536 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 4 ms 428 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 3 ms 348 KB Output is correct
16 Correct 6 ms 604 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 370 ms 7484 KB Output is correct
20 Correct 169 ms 8644 KB Output is correct
21 Correct 363 ms 10104 KB Output is correct
22 Correct 106 ms 11092 KB Output is correct
23 Correct 415 ms 19028 KB Output is correct
24 Correct 634 ms 13904 KB Output is correct
25 Correct 14 ms 3672 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1574 ms 7492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 1545 ms 7344 KB Time limit exceeded
3 Halted 0 ms 0 KB -