oj.uz

Submission #593309

# Submission time Handle Problem Language Result Execution time Memory
593309 2022-07-10T20:33:11 Z MohammadAghil Event Hopping (BOI22_events) C++17
30 / 100
 232 ms 30120 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++;
    
    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({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];
        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 1876 KB Output is correct
2 Correct 138 ms 20912 KB Output is correct
3 Correct 139 ms 24240 KB Output is correct
4 Correct 166 ms 24696 KB Output is correct
5 Correct 143 ms 24728 KB Output is correct
6 Correct 146 ms 25208 KB Output is correct
7 Correct 144 ms 25332 KB Output is correct
8 Correct 172 ms 29452 KB Output is correct
9 Correct 156 ms 29320 KB Output is correct
10 Correct 158 ms 25420 KB Output is correct
11 Incorrect 173 ms 27356 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 2004 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 2076 KB Output is correct
7 Correct 3 ms 2132 KB Output is correct
8 Correct 2 ms 2088 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 2004 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 2076 KB Output is correct
7 Correct 3 ms 2132 KB Output is correct
8 Correct 2 ms 2088 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 1840 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 1988 KB Output is correct
15 Correct 2 ms 2004 KB Output is correct
16 Correct 2 ms 2092 KB Output is correct
17 Correct 2 ms 2132 KB Output is correct
18 Correct 1 ms 2004 KB Output is correct
19 Correct 34 ms 5788 KB Output is correct
20 Correct 35 ms 5760 KB Output is correct
21 Correct 37 ms 6220 KB Output is correct
22 Incorrect 30 ms 6280 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 2004 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 2076 KB Output is correct
7 Correct 3 ms 2132 KB Output is correct
8 Correct 2 ms 2088 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 2008 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 2072 KB Output is correct
16 Correct 2 ms 2004 KB Output is correct
17 Correct 2 ms 2132 KB Output is correct
18 Correct 2 ms 1944 KB Output is correct
19 Correct 117 ms 19776 KB Output is correct
20 Correct 111 ms 20248 KB Output is correct
21 Correct 114 ms 20788 KB Output is correct
22 Incorrect 118 ms 22608 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 135 ms 21012 KB Output is correct
2 Correct 141 ms 24228 KB Output is correct
3 Correct 172 ms 24692 KB Output is correct
4 Correct 166 ms 29256 KB Output is correct
5 Correct 157 ms 25448 KB Output is correct
6 Correct 232 ms 29968 KB Output is correct
7 Correct 214 ms 29928 KB Output is correct
8 Correct 195 ms 30120 KB Output is correct
9 Correct 149 ms 25648 KB Output is correct
10 Correct 186 ms 28748 KB Output is correct
11 Correct 190 ms 28524 KB Output is correct
12 Correct 192 ms 28680 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 138 ms 20912 KB Output is correct
3 Correct 139 ms 24240 KB Output is correct
4 Correct 166 ms 24696 KB Output is correct
5 Correct 143 ms 24728 KB Output is correct
6 Correct 146 ms 25208 KB Output is correct
7 Correct 144 ms 25332 KB Output is correct
8 Correct 172 ms 29452 KB Output is correct
9 Correct 156 ms 29320 KB Output is correct
10 Correct 158 ms 25420 KB Output is correct
11 Incorrect 173 ms 27356 KB Output isn't correct
12 Halted 0 ms 0 KB -