oj.uz

Submission #593323

# Submission time Handle Problem Language Result Execution time Memory
593323 2022-07-10T21:16:55 Z MohammadAghil Event Hopping (BOI22_events) C++17
10 / 100
 189 ms 28016 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 = 2e5 + 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 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<<1) 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);
    
    vector<vector<pp>> query(n);
    vector<int> ans(q, -1);
    rep(i,0,q){
        int l, r; cin >> l >> r; l--, r--;
        query[inv[r]].pb({inv[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(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);
        for(auto[s, ID]: query[i]){
            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 2 ms 3412 KB Output is correct
2 Correct 156 ms 22512 KB Output is correct
3 Correct 161 ms 22720 KB Output is correct
4 Correct 185 ms 23220 KB Output is correct
5 Incorrect 158 ms 22848 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3540 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 2 ms 3540 KB Output is correct
7 Correct 3 ms 3672 KB Output is correct
8 Correct 3 ms 3668 KB Output is correct
9 Correct 2 ms 3540 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3540 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 2 ms 3540 KB Output is correct
7 Correct 3 ms 3672 KB Output is correct
8 Correct 3 ms 3668 KB Output is correct
9 Correct 2 ms 3540 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 3 ms 3540 KB Output is correct
13 Correct 2 ms 3540 KB Output is correct
14 Correct 2 ms 3540 KB Output is correct
15 Correct 3 ms 3540 KB Output is correct
16 Correct 3 ms 3668 KB Output is correct
17 Correct 3 ms 3668 KB Output is correct
18 Correct 2 ms 3540 KB Output is correct
19 Correct 36 ms 6396 KB Output is correct
20 Correct 37 ms 6328 KB Output is correct
21 Correct 37 ms 6860 KB Output is correct
22 Incorrect 34 ms 6960 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 3 ms 3540 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 2 ms 3540 KB Output is correct
6 Correct 2 ms 3540 KB Output is correct
7 Correct 3 ms 3672 KB Output is correct
8 Correct 3 ms 3668 KB Output is correct
9 Correct 2 ms 3540 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 2 ms 3412 KB Output is correct
12 Correct 3 ms 3540 KB Output is correct
13 Correct 3 ms 3540 KB Output is correct
14 Correct 3 ms 3540 KB Output is correct
15 Correct 3 ms 3540 KB Output is correct
16 Correct 3 ms 3668 KB Output is correct
17 Correct 3 ms 3668 KB Output is correct
18 Correct 2 ms 3540 KB Output is correct
19 Correct 167 ms 20584 KB Output is correct
20 Correct 125 ms 20596 KB Output is correct
21 Correct 142 ms 20688 KB Output is correct
22 Incorrect 142 ms 22688 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 22592 KB Output is correct
2 Correct 188 ms 22856 KB Output is correct
3 Correct 189 ms 23140 KB Output is correct
4 Incorrect 181 ms 28016 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 156 ms 22512 KB Output is correct
3 Correct 161 ms 22720 KB Output is correct
4 Correct 185 ms 23220 KB Output is correct
5 Incorrect 158 ms 22848 KB Output isn't correct
6 Halted 0 ms 0 KB -