oj.uz

Submission #993068

# Submission time Handle Problem Language Result Execution time Memory
993068 2024-06-05T09:40:28 Z amine_aroua Event Hopping (BOI22_events) C++17
20 / 100
 493 ms 120244 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];
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>> koll;
    fore(i , n)
    {
        cin>>v[i].first>>v[i].second;
        koll.pb({v[i].first , 0 , i});
        koll.pb({v[i].second , 1 , i});
    }
    sort(koll.begin() , koll.end());
    int cnt = 0;
    for(auto [x , t , 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 62 ms 109624 KB Output is correct
2 Correct 366 ms 119160 KB Output is correct
3 Correct 421 ms 119220 KB Output is correct
4 Correct 480 ms 119220 KB Output is correct
5 Incorrect 477 ms 119244 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 109616 KB Output is correct
2 Correct 47 ms 109620 KB Output is correct
3 Correct 48 ms 109872 KB Output is correct
4 Correct 46 ms 109876 KB Output is correct
5 Correct 51 ms 109872 KB Output is correct
6 Incorrect 64 ms 109876 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 109616 KB Output is correct
2 Correct 47 ms 109620 KB Output is correct
3 Correct 48 ms 109872 KB Output is correct
4 Correct 46 ms 109876 KB Output is correct
5 Correct 51 ms 109872 KB Output is correct
6 Incorrect 64 ms 109876 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 109616 KB Output is correct
2 Correct 47 ms 109620 KB Output is correct
3 Correct 48 ms 109872 KB Output is correct
4 Correct 46 ms 109876 KB Output is correct
5 Correct 51 ms 109872 KB Output is correct
6 Incorrect 64 ms 109876 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 367 ms 118704 KB Output is correct
2 Correct 435 ms 119952 KB Output is correct
3 Correct 481 ms 118820 KB Output is correct
4 Correct 331 ms 119196 KB Output is correct
5 Correct 465 ms 119472 KB Output is correct
6 Correct 441 ms 120244 KB Output is correct
7 Correct 441 ms 119472 KB Output is correct
8 Correct 493 ms 118988 KB Output is correct
9 Correct 275 ms 117648 KB Output is correct
10 Correct 402 ms 119436 KB Output is correct
11 Correct 397 ms 118700 KB Output is correct
12 Correct 414 ms 119688 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 109624 KB Output is correct
2 Correct 366 ms 119160 KB Output is correct
3 Correct 421 ms 119220 KB Output is correct
4 Correct 480 ms 119220 KB Output is correct
5 Incorrect 477 ms 119244 KB Output isn't correct
6 Halted 0 ms 0 KB -