oj.uz

Submission #993015

# Submission time Handle Problem Language Result Execution time Memory
993015 2024-06-05T08:59:00 Z amine_aroua Event Hopping (BOI22_events) C++17
20 / 100
 503 ms 121764 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(s == e)
        {
            cout<<0<<nl;
            continue;
        }
        if(v[s].second > v[e].second)
        {
            cout<<"impossible"<<nl;
            continue;
        }
        if(v[e].first <= v[s].first && v[s].second <= v[e].second)
        {
            cout<<1<<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 52 ms 109624 KB Output is correct
2 Correct 403 ms 121476 KB Output is correct
3 Correct 418 ms 119988 KB Output is correct
4 Correct 482 ms 120852 KB Output is correct
5 Incorrect 457 ms 120496 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 109616 KB Output is correct
2 Correct 47 ms 109708 KB Output is correct
3 Correct 50 ms 109876 KB Output is correct
4 Correct 49 ms 109872 KB Output is correct
5 Incorrect 53 ms 109880 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 109616 KB Output is correct
2 Correct 47 ms 109708 KB Output is correct
3 Correct 50 ms 109876 KB Output is correct
4 Correct 49 ms 109872 KB Output is correct
5 Incorrect 53 ms 109880 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 109616 KB Output is correct
2 Correct 47 ms 109708 KB Output is correct
3 Correct 50 ms 109876 KB Output is correct
4 Correct 49 ms 109872 KB Output is correct
5 Incorrect 53 ms 109880 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 409 ms 121336 KB Output is correct
2 Correct 459 ms 120732 KB Output is correct
3 Correct 486 ms 121032 KB Output is correct
4 Correct 276 ms 121764 KB Output is correct
5 Correct 483 ms 120268 KB Output is correct
6 Correct 448 ms 120580 KB Output is correct
7 Correct 502 ms 120164 KB Output is correct
8 Correct 503 ms 120648 KB Output is correct
9 Correct 243 ms 118772 KB Output is correct
10 Correct 425 ms 119820 KB Output is correct
11 Correct 449 ms 119484 KB Output is correct
12 Correct 486 ms 120924 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 109624 KB Output is correct
2 Correct 403 ms 121476 KB Output is correct
3 Correct 418 ms 119988 KB Output is correct
4 Correct 482 ms 120852 KB Output is correct
5 Incorrect 457 ms 120496 KB Output isn't correct
6 Halted 0 ms 0 KB -