oj.uz

Submission #593330

# Submission time Handle Problem Language Result Execution time Memory
593330 2022-07-10T21:52:51 Z MohammadAghil Event Hopping (BOI22_events) C++17
30 / 100
 262 ms 38092 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);

    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);
    }
    
    while(q--){
        int l, r; cin >> l >> r; l = inv[--l], r = inv[--r];
        if(l == r) cout << 0 << '\n';
        else if(l > r) cout << "impossible\n";
        else{
            auto chk = [&](int i, int j){
                return trk[id[i]].ff >= trk[id[j]].ss;
            };
            if(chk(l, r)) {
                cout << 1 << '\n';
                continue;
            }
            int ans = 0;
            per(i,lg-1,0) if(!chk(l, nxt[r][i])) r = nxt[r][i], ans |= 1<<i;
            if(!chk(l, nxt[r][0])) cout << "impossible\n";
            else if(chk(l, r)) cout << ans + 1 << '\n';
            else cout << ans + 2 << '\n';
        }
    }
    
    return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:83:36: warning: operation on 'l' may be undefined [-Wsequence-point]
   83 |         int l, r; cin >> l >> r; l = inv[--l], r = inv[--r];
events.cpp:83:50: warning: operation on 'r' may be undefined [-Wsequence-point]
   83 |         int l, r; cin >> l >> r; l = inv[--l], r = inv[--r];

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 176 ms 33020 KB Output is correct
3 Correct 167 ms 32816 KB Output is correct
4 Correct 204 ms 32836 KB Output is correct
5 Correct 172 ms 33372 KB Output is correct
6 Correct 180 ms 33872 KB Output is correct
7 Correct 173 ms 34008 KB Output is correct
8 Correct 186 ms 38028 KB Output is correct
9 Correct 182 ms 37992 KB Output is correct
10 Correct 181 ms 33228 KB Output is correct
11 Incorrect 188 ms 35108 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 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 16040 KB Output is correct
4 Correct 8 ms 16044 KB Output is correct
5 Correct 8 ms 16132 KB Output is correct
6 Correct 9 ms 16084 KB Output is correct
7 Correct 9 ms 16144 KB Output is correct
8 Correct 9 ms 16176 KB Output is correct
9 Correct 9 ms 16004 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 16040 KB Output is correct
4 Correct 8 ms 16044 KB Output is correct
5 Correct 8 ms 16132 KB Output is correct
6 Correct 9 ms 16084 KB Output is correct
7 Correct 9 ms 16144 KB Output is correct
8 Correct 9 ms 16176 KB Output is correct
9 Correct 9 ms 16004 KB Output is correct
10 Correct 9 ms 15944 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 9 ms 16084 KB Output is correct
13 Correct 9 ms 16124 KB Output is correct
14 Correct 9 ms 16152 KB Output is correct
15 Correct 9 ms 16136 KB Output is correct
16 Correct 10 ms 16120 KB Output is correct
17 Correct 11 ms 16184 KB Output is correct
18 Correct 9 ms 16000 KB Output is correct
19 Correct 43 ms 17520 KB Output is correct
20 Correct 40 ms 17460 KB Output is correct
21 Correct 42 ms 17724 KB Output is correct
22 Incorrect 36 ms 17792 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 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 16040 KB Output is correct
4 Correct 8 ms 16044 KB Output is correct
5 Correct 8 ms 16132 KB Output is correct
6 Correct 9 ms 16084 KB Output is correct
7 Correct 9 ms 16144 KB Output is correct
8 Correct 9 ms 16176 KB Output is correct
9 Correct 9 ms 16004 KB Output is correct
10 Correct 8 ms 15924 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 8 ms 16084 KB Output is correct
13 Correct 9 ms 16040 KB Output is correct
14 Correct 9 ms 16048 KB Output is correct
15 Correct 8 ms 16048 KB Output is correct
16 Correct 9 ms 16212 KB Output is correct
17 Correct 9 ms 16084 KB Output is correct
18 Correct 9 ms 16012 KB Output is correct
19 Correct 142 ms 32368 KB Output is correct
20 Correct 137 ms 32164 KB Output is correct
21 Correct 148 ms 32204 KB Output is correct
22 Incorrect 147 ms 33952 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 167 ms 32988 KB Output is correct
2 Correct 163 ms 32828 KB Output is correct
3 Correct 181 ms 32764 KB Output is correct
4 Correct 181 ms 38092 KB Output is correct
5 Correct 182 ms 33292 KB Output is correct
6 Correct 242 ms 37740 KB Output is correct
7 Correct 262 ms 37904 KB Output is correct
8 Correct 231 ms 37764 KB Output is correct
9 Correct 184 ms 36868 KB Output is correct
10 Correct 227 ms 37292 KB Output is correct
11 Correct 231 ms 37068 KB Output is correct
12 Correct 219 ms 37280 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 176 ms 33020 KB Output is correct
3 Correct 167 ms 32816 KB Output is correct
4 Correct 204 ms 32836 KB Output is correct
5 Correct 172 ms 33372 KB Output is correct
6 Correct 180 ms 33872 KB Output is correct
7 Correct 173 ms 34008 KB Output is correct
8 Correct 186 ms 38028 KB Output is correct
9 Correct 182 ms 37992 KB Output is correct
10 Correct 181 ms 33228 KB Output is correct
11 Incorrect 188 ms 35108 KB Output isn't correct
12 Halted 0 ms 0 KB -