oj.uz

Submission #593324

# Submission time Handle Problem Language Result Execution time Memory
593324 2022-07-10T21:21:00 Z MohammadAghil Event Hopping (BOI22_events) C++17
30 / 100
 246 ms 31760 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<<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 3 ms 6484 KB Output is correct
2 Correct 156 ms 25724 KB Output is correct
3 Correct 164 ms 25888 KB Output is correct
4 Correct 184 ms 26348 KB Output is correct
5 Correct 161 ms 26412 KB Output is correct
6 Correct 175 ms 26816 KB Output is correct
7 Correct 178 ms 27040 KB Output is correct
8 Correct 182 ms 31120 KB Output is correct
9 Correct 179 ms 31116 KB Output is correct
10 Correct 177 ms 27084 KB Output is correct
11 Incorrect 186 ms 29044 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 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6740 KB Output is correct
4 Correct 4 ms 6740 KB Output is correct
5 Correct 4 ms 6740 KB Output is correct
6 Correct 4 ms 6740 KB Output is correct
7 Correct 4 ms 6740 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Correct 3 ms 6612 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6740 KB Output is correct
4 Correct 4 ms 6740 KB Output is correct
5 Correct 4 ms 6740 KB Output is correct
6 Correct 4 ms 6740 KB Output is correct
7 Correct 4 ms 6740 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Correct 3 ms 6612 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 3 ms 6484 KB Output is correct
12 Correct 4 ms 6740 KB Output is correct
13 Correct 5 ms 6740 KB Output is correct
14 Correct 5 ms 6740 KB Output is correct
15 Correct 4 ms 6740 KB Output is correct
16 Correct 6 ms 6768 KB Output is correct
17 Correct 4 ms 6740 KB Output is correct
18 Correct 4 ms 6612 KB Output is correct
19 Correct 36 ms 9556 KB Output is correct
20 Correct 38 ms 9468 KB Output is correct
21 Correct 38 ms 9932 KB Output is correct
22 Incorrect 31 ms 10068 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 4 ms 6740 KB Output is correct
4 Correct 4 ms 6740 KB Output is correct
5 Correct 4 ms 6740 KB Output is correct
6 Correct 4 ms 6740 KB Output is correct
7 Correct 4 ms 6740 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Correct 3 ms 6612 KB Output is correct
10 Correct 3 ms 6484 KB Output is correct
11 Correct 3 ms 6512 KB Output is correct
12 Correct 4 ms 6740 KB Output is correct
13 Correct 4 ms 6720 KB Output is correct
14 Correct 4 ms 6740 KB Output is correct
15 Correct 4 ms 6656 KB Output is correct
16 Correct 4 ms 6752 KB Output is correct
17 Correct 4 ms 6740 KB Output is correct
18 Correct 4 ms 6612 KB Output is correct
19 Correct 134 ms 23756 KB Output is correct
20 Correct 126 ms 23780 KB Output is correct
21 Correct 145 ms 23736 KB Output is correct
22 Incorrect 150 ms 25488 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 155 ms 25720 KB Output is correct
2 Correct 163 ms 25804 KB Output is correct
3 Correct 187 ms 26316 KB Output is correct
4 Correct 182 ms 31064 KB Output is correct
5 Correct 179 ms 27056 KB Output is correct
6 Correct 239 ms 31620 KB Output is correct
7 Correct 246 ms 31740 KB Output is correct
8 Correct 220 ms 31760 KB Output is correct
9 Correct 181 ms 28388 KB Output is correct
10 Correct 221 ms 30344 KB Output is correct
11 Correct 235 ms 30156 KB Output is correct
12 Correct 225 ms 30284 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 156 ms 25724 KB Output is correct
3 Correct 164 ms 25888 KB Output is correct
4 Correct 184 ms 26348 KB Output is correct
5 Correct 161 ms 26412 KB Output is correct
6 Correct 175 ms 26816 KB Output is correct
7 Correct 178 ms 27040 KB Output is correct
8 Correct 182 ms 31120 KB Output is correct
9 Correct 179 ms 31116 KB Output is correct
10 Correct 177 ms 27084 KB Output is correct
11 Incorrect 186 ms 29044 KB Output isn't correct
12 Halted 0 ms 0 KB -