oj.uz

Submission #972825

# Submission time Handle Problem Language Result Execution time Memory
972825 2024-05-01T08:35:07 Z idas Event Hopping (BOI22_events) C++11
20 / 100
 344 ms 37276 KB 
#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) int((x).size())
#define pb push_back
#define s second
#define f first

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;

const int INF=1e9;

const int N=1e5+10, L=18;
int n, q, s[N], e[N], bl[L][N];
map<int, int> c; int idx;
pii t[8*N];

void upd(int p, pii x, int l=1, int r=idx, int id=1)
{
    if(l==r){
        t[id]=x;
        return;
    }
    int m=(l+r)/2;
    if(p<=m) upd(p, x, l, m, id*2);
    else upd(p, x, m+1, r, id*2+1);
    t[id]=min(t[id*2], t[id*2+1]);
}

pii get(int x, int y, int l=1, int r=idx, int id=1)
{
    if(r<x||l>y) return {INF,INF};
    if(x<=l&&r<=y) return t[id];
    int m=(l+r)/2;
    return min(
        get(x, y, l, m, id*2),
        get(x, y, m+1, r, id*2+1)
    );
}

void build()
{
    FOR(i, 1, L)
    {
        FOR(j, 0, n)
        {
            bl[i][j]=bl[i-1][bl[i-1][j]];
        }
    }
}

int ans(int a, int b)
{
    if(a==b) return 0;
    if(s[b]<=e[a] && e[a]<=e[b]) return 1;
    if(e[a]>e[b]) return INF;

    int ret=0;
    for(int i=L-1; i>=0; i--){
        int k=bl[i][b];

        if(s[k]<=e[a]) continue;

        b=k; ret+=1<<i;
    }

    b=bl[0][b]; ret++;

    if(s[b]<=e[a]) return ret+1;

    return INF;
}

int main()
{
    FAST_IO;
    cin >> n >> q;
    set<int> dif;
    FOR(i, 0, n)
    {
        cin >> s[i] >> e[i];
        dif.insert(s[i]);
        dif.insert(e[i]);
    }

    for(auto it : dif) c[it]=++idx;

    FOR(i, 0, 8*N) t[i]={INF,INF};

    FOR(i, 0, n)
    {
        upd(c[e[i]], {s[i],i});
    }

    FOR(i, 0, n)
    {
        pii ret=get(c[s[i]], c[e[i]]);
        int in=ret.s;
        bl[0][i]=in;
//        cout << i << ": " << in << endl;
    }

    build();

    while(q--){
        int a, b; cin >> a >> b; --a; --b;
        int k=ans(a, b);
        if(k==INF){
            cout << "impossible\n";
        }
        else{
            cout << k << '\n';
        }
    }
}
/*
2 1
1 4
2 3
1 2

5 2
1 3
2 4
4 7
7 9
3 7

tst1:
8 1
1 3
3 6
3 7
3 8
3 9
3 10
10 10
1 10

tst2:
3 1
3 4
1 6
4 9

tst3:
5 1
1 8
1 2
2 3
3 4
6 7

tst4:
7 1
1 4
2 4
3 4
4 5
4 6
4 7
7 9

tst5:
5 1
1 2
2 5
2 6
5 8
6 8

tst6:
5 1
1 2
2 3
3 4
4 9
2 8
*/

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Incorrect 2 ms 12888 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 227 ms 27476 KB Output is correct
2 Correct 205 ms 27540 KB Output is correct
3 Correct 289 ms 27388 KB Output is correct
4 Correct 291 ms 37276 KB Output is correct
5 Correct 184 ms 27808 KB Output is correct
6 Correct 289 ms 37116 KB Output is correct
7 Correct 295 ms 36944 KB Output is correct
8 Correct 344 ms 37268 KB Output is correct
9 Correct 276 ms 35248 KB Output is correct
10 Correct 312 ms 36616 KB Output is correct
11 Correct 298 ms 36428 KB Output is correct
12 Correct 294 ms 36684 KB Output is correct

Subtask #6
0 / 30.0

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