oj.uz

Submission #593325

# Submission time Handle Problem Language Result Execution time Memory
593325 2022-07-10T21:25:19 Z MohammadAghil Event Hopping (BOI22_events) C++17
30 / 100
 269 ms 42240 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 = 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);
    
    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 7 ms 15956 KB Output is correct
2 Correct 168 ms 36172 KB Output is correct
3 Correct 178 ms 36464 KB Output is correct
4 Correct 190 ms 36836 KB Output is correct
5 Correct 180 ms 36940 KB Output is correct
6 Correct 170 ms 37452 KB Output is correct
7 Correct 172 ms 37616 KB Output is correct
8 Correct 196 ms 41564 KB Output is correct
9 Correct 194 ms 41600 KB Output is correct
10 Correct 186 ms 37700 KB Output is correct
11 Incorrect 199 ms 39552 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15856 KB Output is correct
2 Correct 9 ms 15956 KB Output is correct
3 Correct 8 ms 16084 KB Output is correct
4 Correct 9 ms 16104 KB Output is correct
5 Correct 9 ms 16088 KB Output is correct
6 Correct 9 ms 16084 KB Output is correct
7 Correct 9 ms 16212 KB Output is correct
8 Correct 9 ms 16220 KB Output is correct
9 Correct 8 ms 16016 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15856 KB Output is correct
2 Correct 9 ms 15956 KB Output is correct
3 Correct 8 ms 16084 KB Output is correct
4 Correct 9 ms 16104 KB Output is correct
5 Correct 9 ms 16088 KB Output is correct
6 Correct 9 ms 16084 KB Output is correct
7 Correct 9 ms 16212 KB Output is correct
8 Correct 9 ms 16220 KB Output is correct
9 Correct 8 ms 16016 KB Output is correct
10 Correct 8 ms 15956 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 8 ms 16052 KB Output is correct
13 Correct 8 ms 16084 KB Output is correct
14 Correct 8 ms 16060 KB Output is correct
15 Correct 9 ms 16084 KB Output is correct
16 Correct 10 ms 16212 KB Output is correct
17 Correct 10 ms 16212 KB Output is correct
18 Correct 8 ms 16084 KB Output is correct
19 Correct 40 ms 18876 KB Output is correct
20 Correct 41 ms 18880 KB Output is correct
21 Correct 42 ms 19404 KB Output is correct
22 Incorrect 37 ms 19476 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15856 KB Output is correct
2 Correct 9 ms 15956 KB Output is correct
3 Correct 8 ms 16084 KB Output is correct
4 Correct 9 ms 16104 KB Output is correct
5 Correct 9 ms 16088 KB Output is correct
6 Correct 9 ms 16084 KB Output is correct
7 Correct 9 ms 16212 KB Output is correct
8 Correct 9 ms 16220 KB Output is correct
9 Correct 8 ms 16016 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 8 ms 16052 KB Output is correct
13 Correct 8 ms 16136 KB Output is correct
14 Correct 9 ms 16084 KB Output is correct
15 Correct 8 ms 16084 KB Output is correct
16 Correct 10 ms 16188 KB Output is correct
17 Correct 9 ms 16200 KB Output is correct
18 Correct 8 ms 16084 KB Output is correct
19 Correct 139 ms 34284 KB Output is correct
20 Correct 132 ms 34268 KB Output is correct
21 Correct 156 ms 34352 KB Output is correct
22 Incorrect 155 ms 36172 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 36288 KB Output is correct
2 Correct 170 ms 36428 KB Output is correct
3 Correct 200 ms 36920 KB Output is correct
4 Correct 181 ms 41660 KB Output is correct
5 Correct 182 ms 37648 KB Output is correct
6 Correct 269 ms 42140 KB Output is correct
7 Correct 247 ms 42188 KB Output is correct
8 Correct 224 ms 42240 KB Output is correct
9 Correct 186 ms 38960 KB Output is correct
10 Correct 218 ms 40960 KB Output is correct
11 Correct 235 ms 40784 KB Output is correct
12 Correct 225 ms 40968 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 168 ms 36172 KB Output is correct
3 Correct 178 ms 36464 KB Output is correct
4 Correct 190 ms 36836 KB Output is correct
5 Correct 180 ms 36940 KB Output is correct
6 Correct 170 ms 37452 KB Output is correct
7 Correct 172 ms 37616 KB Output is correct
8 Correct 196 ms 41564 KB Output is correct
9 Correct 194 ms 41600 KB Output is correct
10 Correct 186 ms 37700 KB Output is correct
11 Incorrect 199 ms 39552 KB Output isn't correct
12 Halted 0 ms 0 KB -