oj.uz

Submission #992979

# Submission time Handle Problem Language Result Execution time Memory
992979 2024-06-05T08:43:43 Z amine_aroua Event Hopping (BOI22_events) C++17
20 / 100
 655 ms 119472 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<<17))
            cout<<"impossible"<<nl;
        else
            cout<<ans<<nl;
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 109620 KB Output is correct
2 Correct 421 ms 118188 KB Output is correct
3 Correct 457 ms 118168 KB Output is correct
4 Correct 602 ms 118196 KB Output is correct
5 Incorrect 513 ms 118192 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 109692 KB Output is correct
2 Correct 57 ms 109736 KB Output is correct
3 Correct 50 ms 109724 KB Output is correct
4 Correct 77 ms 109872 KB Output is correct
5 Incorrect 74 ms 109876 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 109692 KB Output is correct
2 Correct 57 ms 109736 KB Output is correct
3 Correct 50 ms 109724 KB Output is correct
4 Correct 77 ms 109872 KB Output is correct
5 Incorrect 74 ms 109876 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 109692 KB Output is correct
2 Correct 57 ms 109736 KB Output is correct
3 Correct 50 ms 109724 KB Output is correct
4 Correct 77 ms 109872 KB Output is correct
5 Incorrect 74 ms 109876 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 427 ms 118452 KB Output is correct
2 Correct 536 ms 118632 KB Output is correct
3 Correct 508 ms 118432 KB Output is correct
4 Correct 364 ms 119472 KB Output is correct
5 Correct 518 ms 119468 KB Output is correct
6 Correct 489 ms 119216 KB Output is correct
7 Correct 511 ms 118960 KB Output is correct
8 Correct 655 ms 118980 KB Output is correct
9 Correct 263 ms 117936 KB Output is correct
10 Correct 480 ms 117932 KB Output is correct
11 Correct 477 ms 118076 KB Output is correct
12 Correct 542 ms 118212 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 109620 KB Output is correct
2 Correct 421 ms 118188 KB Output is correct
3 Correct 457 ms 118168 KB Output is correct
4 Correct 602 ms 118196 KB Output is correct
5 Incorrect 513 ms 118192 KB Output isn't correct
6 Halted 0 ms 0 KB -