oj.uz

Submission #992958

# Submission time Handle Problem Language Result Execution time Memory
992958 2024-06-05T08:35:25 Z amine_aroua Event Hopping (BOI22_events) C++17
20 / 100
 480 ms 122964 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 , 0);
        fore(i  , (int)a.size())
            tree[i + BASE] = a[i];
        forn(i  , BASE - 1 , 1)
            tree[i] = max(tree[2*i] , tree[2*i +1]);
    }
    int query(int l , int r)
    {
        if(l > r)
            return 0;
        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 = max(lt , tree[l +1]);
            }
            if(r%2 == 1)
                rt = max(tree[r - 1] ,rt);
            l>>=1;
            r>>=1;
        }
        return max(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));
    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});
    }
    vector<pair<int ,int>> iv = v;
    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++;
    }
    fore(i , n)
    {
        adj[0][v[i].first] = v[i].second;
    }
    forr(i , 1 , 19)
    {
        tree[i - 1].init(N , adj[i - 1]);
        fore(j , N)
        {
            adj[i][j] = tree[i - 1].query(j , adj[i - 1][j]);
        }
    }
    while(q--)
    {
        int s , e;
        cin>>s>>e;
        s-- , e--;
        if(v[s].second > v[e].second)
        {
            cout<<"impossible"<<nl;
            continue;
        }
        int cur = v[s].first;
        s = v[s].first;
        e = v[e].second;
        int ans = 0;
        forn(i , 18 , 0)
        {
            int ns = tree[i].query(s , cur);
            if(ns >= e)
                continue;
            cur = ns;
            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 48 ms 109624 KB Output is correct
2 Correct 414 ms 122332 KB Output is correct
3 Correct 420 ms 121264 KB Output is correct
4 Correct 458 ms 121484 KB Output is correct
5 Incorrect 444 ms 122800 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 109624 KB Output is correct
2 Correct 47 ms 109620 KB Output is correct
3 Correct 48 ms 109784 KB Output is correct
4 Correct 51 ms 109880 KB Output is correct
5 Incorrect 50 ms 109872 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 109624 KB Output is correct
2 Correct 47 ms 109620 KB Output is correct
3 Correct 48 ms 109784 KB Output is correct
4 Correct 51 ms 109880 KB Output is correct
5 Incorrect 50 ms 109872 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 109624 KB Output is correct
2 Correct 47 ms 109620 KB Output is correct
3 Correct 48 ms 109784 KB Output is correct
4 Correct 51 ms 109880 KB Output is correct
5 Incorrect 50 ms 109872 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 122032 KB Output is correct
2 Correct 438 ms 122036 KB Output is correct
3 Correct 455 ms 121868 KB Output is correct
4 Correct 279 ms 122292 KB Output is correct
5 Correct 426 ms 122964 KB Output is correct
6 Correct 437 ms 121432 KB Output is correct
7 Correct 463 ms 121268 KB Output is correct
8 Correct 480 ms 121520 KB Output is correct
9 Correct 249 ms 119472 KB Output is correct
10 Correct 411 ms 121520 KB Output is correct
11 Correct 410 ms 120872 KB Output is correct
12 Correct 417 ms 121264 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 109624 KB Output is correct
2 Correct 414 ms 122332 KB Output is correct
3 Correct 420 ms 121264 KB Output is correct
4 Correct 458 ms 121484 KB Output is correct
5 Incorrect 444 ms 122800 KB Output isn't correct
6 Halted 0 ms 0 KB -