Submission #593330

#	Time	Username	Problem	Language	Result	Execution time	Memory
593330		MohammadAghil	Event Hopping (BOI22_events)	C++17	30 / 100	262 ms	38092 KiB

events

#include <iostream>
#include <algorithm>
#include <functional>
#include <random>
#include <cmath>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <string>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <limits.h>
#include <tuple>
//   #pragma GCC optimization ("unroll-loops")
//  #pragma GCC optimization ("O3")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define per(i,r,l) for(int i = (r); i >= (l); i--)
  #define rep(i,l,r) for(int i = (l); i < (r); i++)
     #define all(x) begin(x), end(x)
        #define sz(x) (int)(x).size()
            #define pb push_back
                #define ss second
                     #define ff first
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 5e5 + 5, lg = 25, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

pp seg[maxn<<2];

void upd(int i, pp k, int x = 1, int lx = 0, int rx = maxn){
    if(lx + 1 == rx) {
        seg[x] = min(seg[x], k);
        return;
    }
    int mid = (lx + rx)>>1;
    if(i < mid) upd(i, k, x<<1, lx, mid);
    else upd(i, k, x<<1|1, mid, rx);
    seg[x] = min(seg[x<<1], seg[x<<1|1]);
}

pp get(int l, int r, int x = 1, int lx = 0, int rx = maxn){
    if(l <= lx && r >= rx) return seg[x];
    int mid = (lx + rx)>>1;
    pp res = {inf, inf};
    if(l < mid) res = get(l, r, x<<1, lx, mid);
    if(mid < r) res = min(res, get(l, r, x<<1|1, mid, rx));
    return res;
}

int nxt[maxn][lg];

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    int n, q; cin >> n >> q;
    rep(i,0,maxn<<2) seg[i] = {inf, inf};
    
    map<int, int> comp;
    vector<pp> trk(n);
    rep(i,0,n) cin >> trk[i].ss >> trk[i].ff, comp[trk[i].ff] = comp[trk[i].ss] = 0;
    vector<int> id(n), inv(n); iota(all(id), 0), sort(all(id), [&](int i, int j){ return trk[i] < trk[j]; });
    rep(i,0,n) inv[id[i]] = i;
    
    int dd = 0;
    for(auto&c:comp) c.ss = dd++;
    assert(dd < maxn);

    rep(i,0,n){
        auto[r, l] = trk[id[i]];
        upd(comp[r], {l, i});
        nxt[i][0] = get(comp[l], comp[r]+1).ss;
        rep(j,1,lg) nxt[i][j] = nxt[nxt[i][j-1]][j-1];
        assert(nxt[i][0] < n);
    }
    
    while(q--){
        int l, r; cin >> l >> r; l = inv[--l], r = inv[--r];
        if(l == r) cout << 0 << '\n';
        else if(l > r) cout << "impossible\n";
        else{
            auto chk = [&](int i, int j){
                return trk[id[i]].ff >= trk[id[j]].ss;
            };
            if(chk(l, r)) {
                cout << 1 << '\n';
                continue;
            }
            int ans = 0;
            per(i,lg-1,0) if(!chk(l, nxt[r][i])) r = nxt[r][i], ans |= 1<<i;
            if(!chk(l, nxt[r][0])) cout << "impossible\n";
            else if(chk(l, r)) cout << ans + 1 << '\n';
            else cout << ans + 2 << '\n';
        }
    }
    
    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:83:36: warning: operation on 'l' may be undefined [-Wsequence-point]
   83 |         int l, r; cin >> l >> r; l = inv[--l], r = inv[--r];
events.cpp:83:50: warning: operation on 'r' may be undefined [-Wsequence-point]
   83 |         int l, r; cin >> l >> r; l = inv[--l], r = inv[--r];

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30