oj.uz

Submission #993072

# Submission time Handle Problem Language Result Execution time Memory
993072 2024-06-05T09:47:04 Z amine_aroua Event Hopping (BOI22_events) C++17
20 / 100
 507 ms 120108 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 ,int>> koll;
    fore(i , n)
    {
        cin>>v[i].first>>v[i].second;
        koll.pb({v[i].first , 0,0 , i});
        koll.pb({v[i].second , 1 ,v[i].first, i});
    }
    sort(koll.begin() , koll.end());
    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 43 ms 109620 KB Output is correct
2 Correct 383 ms 119080 KB Output is correct
3 Correct 495 ms 118576 KB Output is correct
4 Correct 500 ms 118820 KB Output is correct
5 Incorrect 474 ms 119180 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 109588 KB Output is correct
2 Correct 52 ms 109636 KB Output is correct
3 Correct 50 ms 109876 KB Output is correct
4 Correct 51 ms 109880 KB Output is correct
5 Correct 63 ms 109872 KB Output is correct
6 Incorrect 51 ms 109816 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 109588 KB Output is correct
2 Correct 52 ms 109636 KB Output is correct
3 Correct 50 ms 109876 KB Output is correct
4 Correct 51 ms 109880 KB Output is correct
5 Correct 63 ms 109872 KB Output is correct
6 Incorrect 51 ms 109816 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 109588 KB Output is correct
2 Correct 52 ms 109636 KB Output is correct
3 Correct 50 ms 109876 KB Output is correct
4 Correct 51 ms 109880 KB Output is correct
5 Correct 63 ms 109872 KB Output is correct
6 Incorrect 51 ms 109816 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 355 ms 118860 KB Output is correct
2 Correct 440 ms 119588 KB Output is correct
3 Correct 504 ms 118064 KB Output is correct
4 Correct 265 ms 120108 KB Output is correct
5 Correct 457 ms 119588 KB Output is correct
6 Correct 427 ms 119592 KB Output is correct
7 Correct 507 ms 120108 KB Output is correct
8 Correct 480 ms 120020 KB Output is correct
9 Correct 254 ms 119080 KB Output is correct
10 Correct 424 ms 118024 KB Output is correct
11 Correct 415 ms 118752 KB Output is correct
12 Correct 455 ms 117860 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 109620 KB Output is correct
2 Correct 383 ms 119080 KB Output is correct
3 Correct 495 ms 118576 KB Output is correct
4 Correct 500 ms 118820 KB Output is correct
5 Incorrect 474 ms 119180 KB Output isn't correct
6 Halted 0 ms 0 KB -