oj.uz

Submission #593317

# Submission time Handle Problem Language Result Execution time Memory
593317 2022-07-10T21:07:53 Z MohammadAghil Event Hopping (BOI22_events) C++17
30 / 100
 215 ms 27728 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 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++;
    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(dd-comp[r], {l, i});
        nxt[i][0] = get(dd-comp[l]).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 1 ms 1876 KB Output is correct
2 Correct 161 ms 22344 KB Output is correct
3 Correct 139 ms 22004 KB Output is correct
4 Correct 161 ms 22364 KB Output is correct
5 Correct 156 ms 22552 KB Output is correct
6 Correct 154 ms 22924 KB Output is correct
7 Correct 146 ms 23068 KB Output is correct
8 Correct 154 ms 27096 KB Output is correct
9 Correct 154 ms 27160 KB Output is correct
10 Correct 156 ms 23124 KB Output is correct
11 Incorrect 166 ms 25120 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 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 2132 KB Output is correct
4 Correct 2 ms 2004 KB Output is correct
5 Correct 2 ms 2004 KB Output is correct
6 Correct 2 ms 2004 KB Output is correct
7 Correct 2 ms 2004 KB Output is correct
8 Correct 2 ms 2132 KB Output is correct
9 Correct 2 ms 2004 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 2132 KB Output is correct
4 Correct 2 ms 2004 KB Output is correct
5 Correct 2 ms 2004 KB Output is correct
6 Correct 2 ms 2004 KB Output is correct
7 Correct 2 ms 2004 KB Output is correct
8 Correct 2 ms 2132 KB Output is correct
9 Correct 2 ms 2004 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 1 ms 1876 KB Output is correct
12 Correct 2 ms 2004 KB Output is correct
13 Correct 2 ms 2004 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 2 ms 2004 KB Output is correct
16 Correct 2 ms 2004 KB Output is correct
17 Correct 3 ms 2132 KB Output is correct
18 Correct 2 ms 2004 KB Output is correct
19 Correct 38 ms 5724 KB Output is correct
20 Correct 35 ms 5452 KB Output is correct
21 Correct 38 ms 6116 KB Output is correct
22 Incorrect 31 ms 6096 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 2132 KB Output is correct
4 Correct 2 ms 2004 KB Output is correct
5 Correct 2 ms 2004 KB Output is correct
6 Correct 2 ms 2004 KB Output is correct
7 Correct 2 ms 2004 KB Output is correct
8 Correct 2 ms 2132 KB Output is correct
9 Correct 2 ms 2004 KB Output is correct
10 Correct 1 ms 1876 KB Output is correct
11 Correct 1 ms 1876 KB Output is correct
12 Correct 2 ms 2004 KB Output is correct
13 Correct 2 ms 2080 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 2 ms 2004 KB Output is correct
16 Correct 3 ms 2092 KB Output is correct
17 Correct 3 ms 2092 KB Output is correct
18 Correct 2 ms 2004 KB Output is correct
19 Correct 120 ms 20312 KB Output is correct
20 Correct 104 ms 19868 KB Output is correct
21 Correct 119 ms 19876 KB Output is correct
22 Incorrect 126 ms 21744 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 160 ms 22208 KB Output is correct
2 Correct 140 ms 21888 KB Output is correct
3 Correct 162 ms 22320 KB Output is correct
4 Correct 163 ms 27212 KB Output is correct
5 Correct 155 ms 23116 KB Output is correct
6 Correct 213 ms 27684 KB Output is correct
7 Correct 215 ms 27580 KB Output is correct
8 Correct 190 ms 27728 KB Output is correct
9 Correct 142 ms 24528 KB Output is correct
10 Correct 193 ms 26488 KB Output is correct
11 Correct 190 ms 26160 KB Output is correct
12 Correct 177 ms 26420 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 161 ms 22344 KB Output is correct
3 Correct 139 ms 22004 KB Output is correct
4 Correct 161 ms 22364 KB Output is correct
5 Correct 156 ms 22552 KB Output is correct
6 Correct 154 ms 22924 KB Output is correct
7 Correct 146 ms 23068 KB Output is correct
8 Correct 154 ms 27096 KB Output is correct
9 Correct 154 ms 27160 KB Output is correct
10 Correct 156 ms 23124 KB Output is correct
11 Incorrect 166 ms 25120 KB Output isn't correct
12 Halted 0 ms 0 KB -