oj.uz

Submission #993086

# Submission time Handle Problem Language Result Execution time Memory
993086 2024-06-05T10:00:28 Z amine_aroua Event Hopping (BOI22_events) C++17
20 / 100
 531 ms 120100 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'
#define pb push_back
#define fore(i , n) for(int i = 0 ; i< n;i++)
#define forr(i , x , y) for(int i = x; i <= y; i++)
#define forn(i , x , y) for(int i = x; i >= y ; i--)
const int N =2e5 + 10;
struct seg
{
    int BASE;
    vector<int> tree;
    void init(int n , vector<int> &a)
    {
        BASE = n;
        while(__builtin_popcount(BASE) != 1)
        {
            BASE++;
        }
        tree.assign(2*BASE , N);
        fore(i  , (int)a.size())
            tree[i + BASE] = a[i];
        forn(i  , BASE - 1 , 1)
            tree[i] = min(tree[2*i] , tree[2*i +1]);
    }
    int query(int l , int r)
    {
        if(l > r)
            return N;
        l+=BASE;
        r+=BASE;
        if(l == r)
            return tree[l];
        int lt = tree[l] , rt = tree[r];
        while(l + 1 < r)
        {
            if(l %2 == 0)
            {
                lt = min(lt , tree[l +1]);
            }
            if(r%2 == 1)
                rt = min(tree[r - 1] ,rt);
            l>>=1;
            r>>=1;
        }
        return min(lt ,rt);
    }
}tree[19];
bool cmp(const tuple<int ,int,int,int> &a , const tuple<int ,int,int,int> &b)
{
    if(get<0>(a) == get<0>(b))
    {
        if(get<1>(a) == get<1>(b) && get<1>(a) == 1)
        {
            return get<2>(a) < get<2>(b);
        }
        else if(get<1>(a) == get<1>(b) && get<1>(a) == 0)
        {
            return get<2>(a) < get<2>(b);
        }
        return get<1>(a) < get<1>(b);
    }
    return get<0>(a) < get<0>(b);
}
signed main()
{
    int n , q;
    cin>>n>>q;
    map<int , int> compress;
    vector<pair<int ,int>> v(n);
    vector<vector<int>> adj(20 , vector<int>(N , N));
    vector<tuple<int , int,int ,int>> koll;
    fore(i , n)
    {
        cin>>v[i].first>>v[i].second;
        koll.pb({v[i].first , 0,v[i].second , i});
        koll.pb({v[i].second , 1 ,v[i].first, i});
    }
    sort(koll.begin() , koll.end() , cmp);
    int cnt = 0;
    for(auto [x , t ,j, i] : koll)
    {
        if(t == 0)
            v[i].first = cnt++;
        else
            v[i].second = cnt++;
    }
//    int cnt = 0;
//    for(auto p : compress)
//    {
//        compress[p.first] = cnt++;
//    }
    fore(i , n)
    {
//        v[i].first = compress[v[i].first];
//        v[i].second = compress[v[i].second];
        adj[0][v[i].second] = min(adj[0][v[i].second] , v[i].first);
    }
    forr(i , 1 , 19)
    {
        tree[i - 1].init(N , adj[i - 1]);
        forr(j , 0 ,N - 1)
        {
            adj[i][j] = tree[i - 1].query(min(j , adj[i - 1][j]) , j);
        }
    }
    while(q--)
    {
        int s , e;
        cin>>s>>e;
        s-- , e--;
        if(s == e)
        {
            cout<<0<<nl;
            continue;
        }
        if(v[s].second > v[e].second)
        {
            cout<<"impossible"<<nl;
            continue;
        }
        s = v[s].first;
        int cur = v[e].second;
        e = v[e].second;
        int ans = 0;
        forn(i , 18 , 0)
        {
            int ncur = tree[i].query(cur , e);
            if(ncur <= s)
                continue;
            cur = ncur;
            ans+=(1<<i);
        }
        if(ans >= (1<<18))
            cout<<"impossible"<<nl;
        else
            cout<<ans<<nl;
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 109624 KB Output is correct
2 Correct 390 ms 119140 KB Output is correct
3 Correct 432 ms 119548 KB Output is correct
4 Correct 531 ms 119080 KB Output is correct
5 Incorrect 453 ms 119596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 109708 KB Output is correct
2 Correct 60 ms 109624 KB Output is correct
3 Correct 48 ms 109876 KB Output is correct
4 Correct 47 ms 109780 KB Output is correct
5 Correct 48 ms 109876 KB Output is correct
6 Incorrect 48 ms 109884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 109708 KB Output is correct
2 Correct 60 ms 109624 KB Output is correct
3 Correct 48 ms 109876 KB Output is correct
4 Correct 47 ms 109780 KB Output is correct
5 Correct 48 ms 109876 KB Output is correct
6 Incorrect 48 ms 109884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 109708 KB Output is correct
2 Correct 60 ms 109624 KB Output is correct
3 Correct 48 ms 109876 KB Output is correct
4 Correct 47 ms 109780 KB Output is correct
5 Correct 48 ms 109876 KB Output is correct
6 Incorrect 48 ms 109884 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 421 ms 119236 KB Output is correct
2 Correct 443 ms 119648 KB Output is correct
3 Correct 491 ms 118604 KB Output is correct
4 Correct 271 ms 120096 KB Output is correct
5 Correct 459 ms 119844 KB Output is correct
6 Correct 446 ms 120100 KB Output is correct
7 Correct 439 ms 119660 KB Output is correct
8 Correct 506 ms 119340 KB Output is correct
9 Correct 257 ms 117544 KB Output is correct
10 Correct 425 ms 118104 KB Output is correct
11 Correct 413 ms 117832 KB Output is correct
12 Correct 431 ms 118412 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 109624 KB Output is correct
2 Correct 390 ms 119140 KB Output is correct
3 Correct 432 ms 119548 KB Output is correct
4 Correct 531 ms 119080 KB Output is correct
5 Incorrect 453 ms 119596 KB Output isn't correct
6 Halted 0 ms 0 KB -