oj.uz

Submission #1029430

# Submission time Handle Problem Language Result Execution time Memory
1029430 2024-07-20T21:02:40 Z hasan2006 Event Hopping (BOI22_events) C++17
30 / 100
 378 ms 79808 KB 
#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 5e5 + 9 , mod = 1e9 + 7;
ll  dp[N] , a[N] ,c[N] ,  b[N] , p[N][22], A[N] , B[N];
vector<int>vc[N];
void solve()
{
    ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
    cin>>n>>m;
    set<int>sk , ss ,st;
    map<int,int>mp;
    vector<pair<ll,ll>>v;
    for(i = 1; i <= n; i++){
        cin>>a[i]>>b[i];
        ss.insert(a[i]);
        ss.insert(b[i]);
    }
    for(auto it : ss)
        mp[it] = ++s;
    for(i = 1; i <= n; i++){
        a[i] = mp[a[i]] , b[i] = mp[b[i]];
        v.pb({a[i] , b[i]});
        st.insert(b[i]);
    }
    sort(all(v));
    for(auto to : v){
        while(st.size() && *st.begin() < to.fi)
            p[*st.begin()][0] =  mx , st.erase(st.begin());

        mx = max(mx , to.se);
    }
    for(auto it : st)
        p[it][0] = mx;
    ss.clear() , st.clear();
    for(i = s; i >= 1; i--)
        for(j = 1; j <= 20; j++)
            p[i][j] = p[p[i][j - 1]][j - 1];
   for(j = 1; j <= m; j++){
        cin>>A[j]>>B[j];
        l = A[j] , r = B[j];
        if(b[l] > b[r]){
           // cout<<"impossible\n";
            continue;
        }
        if(b[l] >= a[r] && b[l] <= b[r]){
            //cout<<(l != r)<<"\n";
            continue;
        }
        l = b[l];
        s = 0;
        for(i = 20; i >= 0; i--)
            if(p[l][i] && p[l][i] < a[r])
                s += (1 << i) , l = p[l][i];
        if(p[l][0] >= a[r]){
            vc[l].pb(j);
            //cout<<s + 2<<"\n";
        }else {
            //cout<<"impossible\n";
        }
    }
    for(i = 1; i <= n; i++)
        st.insert(b[i]);
    for(auto to : v){
        while(st.size() && *st.begin() < to.fi){
            for(auto to : vc[*st.begin()]){
                l = a[B[to]] , r = b[B[to]];
                auto it = ss.lower_bound(l);
                c[to] = (it != ss.end() && l <= *it && *it <= r);
            }
            st.erase(st.begin());

        }
        ss.insert(to.se);
    }
    for(auto it : st){
        for(auto to : vc[it]){
                l = a[B[to]] , r = b[B[to]];
                auto it1 = ss.lower_bound(l);
                c[to] = (it1 != ss.end() && l <= *it1 && *it1 <= r);
            }
    }

    for(j = 1; j <= m; j++){
    l = A[j] , r = B[j];
        if(b[l] > b[r]){
            cout<<"impossible\n";
            continue;
        }
        if(b[l] >= a[r] && b[l] <= b[r]){
            cout<<(l != r)<<"\n";
            continue;
        }
        l = b[l];
        s = 0;
        for(i = 20; i >= 0; i--)
            if(p[l][i] && p[l][i] < a[r])
                s += (1 << i) , l = p[l][i];
        if(p[l][0] >= a[r] && c[j]){
            cout<<s + 2<<"\n";
        }else {
            cout<<"impossible\n";
        }
    }

}


int main(){
    TL;
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    int t = 1;
//    cin>>t;
    while(t--)
     {
        solve();
     }
}
// Author : حسن

Compilation message

events.cpp: In function 'void solve()':
events.cpp:26:12: warning: unused variable 'q' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |            ^
events.cpp:26:30: warning: unused variable 'x' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                              ^
events.cpp:26:34: warning: unused variable 'y' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                  ^
events.cpp:26:46: warning: unused variable 'f' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                              ^
events.cpp:26:50: warning: unused variable 'k' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                  ^
events.cpp:26:58: warning: unused variable 'mn' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                          ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 222 ms 52708 KB Output is correct
3 Correct 232 ms 52668 KB Output is correct
4 Correct 237 ms 52668 KB Output is correct
5 Correct 221 ms 55260 KB Output is correct
6 Correct 231 ms 57792 KB Output is correct
7 Correct 248 ms 58708 KB Output is correct
8 Correct 258 ms 79808 KB Output is correct
9 Correct 275 ms 78816 KB Output is correct
10 Correct 244 ms 52924 KB Output is correct
11 Correct 325 ms 63508 KB Output is correct
12 Correct 178 ms 49088 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12120 KB Output is correct
2 Correct 6 ms 12124 KB Output is correct
3 Correct 6 ms 12380 KB Output is correct
4 Correct 8 ms 12612 KB Output is correct
5 Incorrect 6 ms 12376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12120 KB Output is correct
2 Correct 6 ms 12124 KB Output is correct
3 Correct 6 ms 12380 KB Output is correct
4 Correct 8 ms 12612 KB Output is correct
5 Incorrect 6 ms 12376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12120 KB Output is correct
2 Correct 6 ms 12124 KB Output is correct
3 Correct 6 ms 12380 KB Output is correct
4 Correct 8 ms 12612 KB Output is correct
5 Incorrect 6 ms 12376 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 229 ms 52648 KB Output is correct
2 Correct 224 ms 52740 KB Output is correct
3 Correct 233 ms 52544 KB Output is correct
4 Correct 286 ms 79032 KB Output is correct
5 Correct 231 ms 52924 KB Output is correct
6 Correct 378 ms 79292 KB Output is correct
7 Correct 349 ms 79324 KB Output is correct
8 Correct 327 ms 79576 KB Output is correct
9 Correct 258 ms 74964 KB Output is correct
10 Correct 304 ms 79036 KB Output is correct
11 Correct 296 ms 78752 KB Output is correct
12 Correct 309 ms 79040 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 222 ms 52708 KB Output is correct
3 Correct 232 ms 52668 KB Output is correct
4 Correct 237 ms 52668 KB Output is correct
5 Correct 221 ms 55260 KB Output is correct
6 Correct 231 ms 57792 KB Output is correct
7 Correct 248 ms 58708 KB Output is correct
8 Correct 258 ms 79808 KB Output is correct
9 Correct 275 ms 78816 KB Output is correct
10 Correct 244 ms 52924 KB Output is correct
11 Correct 325 ms 63508 KB Output is correct
12 Correct 178 ms 49088 KB Output is correct
13 Correct 5 ms 12120 KB Output is correct
14 Correct 6 ms 12124 KB Output is correct
15 Correct 6 ms 12380 KB Output is correct
16 Correct 8 ms 12612 KB Output is correct
17 Incorrect 6 ms 12376 KB Output isn't correct
18 Halted 0 ms 0 KB -