oj.uz

Submission #593298

# Submission time Handle Problem Language Result Execution time Memory
593298 2022-07-10T19:57:31 Z MohammadAghil Event Hopping (BOI22_events) C++17
0 / 100
 147 ms 21916 KB 
#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 = 1e5 + 5, lg = 22, 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 fen[maxn];

void upd(int i, pp k){
    for(i++; i < maxn; i += i&-i) fen[i] = min(fen[i], k);
}

pp get(int i){
    pp res = {inf, inf};
    for(i++; i; i -= i&-i) res = min(res, fen[i]);
    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) fen[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++;
    
    vector<vector<pp>> query(n);
    vector<int> ans(q, -1);
    rep(i,0,q){
        int l, r; cin >> l >> r; l--, r--;
        query[r].pb({l, i});
    }
    auto chk = [&](int i, int j){
        return trk[id[j]].ss <= trk[id[i]].ff;
    };
    rep(i,0,n){
        auto[r, l] = trk[id[i]];
        
        upd(dd-comp[r], {l, i});
        nxt[i][0] = get(dd-comp[l]).ss;
//        cout << i << ' ' << nxt[i][0] << endl;
        rep(j,1,lg) nxt[i][j] = nxt[nxt[i][j-1]][j-1];
        
        for(auto[s, ID]: query[i]){
            s = inv[s];
            if(s > i) continue;
            if(s == i) ans[ID] = 0;
            else{
                int cr = i;
                int res = 0;
                per(j,lg-1,0) if(!chk(s, nxt[cr][j])) cr = nxt[cr][j], res |= 1<<j;
                if(chk(s, nxt[cr][0])){
                    if(s == cr) ans[ID] = res;
                    else if(chk(s, cr)) ans[ID] = res + 1;
                    else ans[ID] = res + 2;
                }
            }
        }
    }
    rep(i,0,q){
        if(ans[i] == -1) cout << "impossible\n";
        else cout << ans[i] << '\n';
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Incorrect 147 ms 21916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Incorrect 2 ms 1236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Incorrect 2 ms 1236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Incorrect 2 ms 1236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 21896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Incorrect 147 ms 21916 KB Output isn't correct
3 Halted 0 ms 0 KB -