oj.uz

Submission #1009441

# Submission time Handle Problem Language Result Execution time Memory
1009441 2024-06-27T14:07:56 Z mispertion Event Hopping (BOI22_events) C++17
25 / 100
 158 ms 80464 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
 
const ld PI = 3.1415926535;
const int N = 1e5+10;
const int M = 7e6 + 1;
int mod = 1e9 + 7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 467743;
 
int mult(int a, int b) {
    return a * 1LL * b % mod;
}
 
int sum(int a, int b) { 
    if(a + b >= mod)
        return a + b - mod;
    if(a + b < 0)
        return a + b + mod;
    return a + b;
}
 
int binpow(int a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return mult(binpow(a, n - 1), a);
    } else {
        int b = binpow(a, n / 2);
        return mult(b, b);
    }
}

const int K = 20;
int n, st[N], en[N], up[N][K], q;
pii mnl[N];

struct sparset{
    pii st[N][K];
    
    void init(int n){
        for(int i = 1; i <= n; i++)
            st[i][0] = mnl[i];
        for(int k = 1; k < K; k++){
            for(int i = 1; i + (1 << k) - 1 <= n; i++)
                st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
        }
    }

    int get(int l, int r){
        int k = __lg(r - l + 1);
        return min(st[l][k], st[r - (1 << k) + 1][k]).S;
    }
};

void solve(){
    cin >> n >> q;
    vector<int> vs = {};
    for(int i = 1; i <= n; i++){
        cin >> st[i] >> en[i];
        vs.pb(st[i]);
        vs.pb(en[i]);
    }
    sort(all(vs));
    vs.resize(unique(all(vs)) - vs.begin());
    for(int i = 1; i <= sz(vs); i++){
        mnl[i] = {infl, 0};
    }
    for(int i = 1; i <= n; i++){
        int ps = upper_bound(all(vs), en[i]) - vs.begin();
        mnl[ps] = min(mnl[ps], {upper_bound(all(vs), st[i]) - vs.begin(), i});
    }
    sparset spr;
    spr.init(sz(vs));
    for(int i = 1; i <= n; i++){
        int l = upper_bound(all(vs), st[i]) - vs.begin(), r = upper_bound(all(vs), en[i]) - vs.begin();
        int ml = spr.get(l, r);
        up[i][0] = ml;
    }    
    for(int k = 1; k < K; k++)
        for(int i = 1; i <= n; i++)
            up[i][k] = up[up[i][k - 1]][k - 1];
    while (q--){
        int s, e;
        cin >> s >> e;
        if(s == e){
            cout << 0 << '\n';
            continue;
        }
        if(st[e] <= en[s] && en[s] <= en[e]){
            cout << 1 << '\n';
            continue;;
        }
        if(en[s] > en[e]){
            cout << "impossible\n";
            continue;
        }
        int sm = 0;
        for(int k = K - 1; k >= 0; k--){
            if(st[up[e][k]] > en[s]){
                e = up[e][k];
                sm += (1 << k);
            }
        }
        e = up[e][0];
        sm++;
        if(st[e] <= en[s] && en[s] <= en[e]){
            cout << 1 + sm << '\n';
        }else{
            cout << "impossible\n";
        }
    }
    
}
 
signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35676 KB Output is correct
2 Correct 112 ms 52744 KB Output is correct
3 Correct 121 ms 52676 KB Output is correct
4 Correct 158 ms 52624 KB Output is correct
5 Runtime error 109 ms 76488 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35676 KB Output is correct
2 Correct 18 ms 35676 KB Output is correct
3 Correct 17 ms 35928 KB Output is correct
4 Correct 17 ms 35676 KB Output is correct
5 Correct 17 ms 35676 KB Output is correct
6 Correct 16 ms 35932 KB Output is correct
7 Correct 17 ms 35928 KB Output is correct
8 Correct 17 ms 35932 KB Output is correct
9 Correct 18 ms 35676 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35676 KB Output is correct
2 Correct 18 ms 35676 KB Output is correct
3 Correct 17 ms 35928 KB Output is correct
4 Correct 17 ms 35676 KB Output is correct
5 Correct 17 ms 35676 KB Output is correct
6 Correct 16 ms 35932 KB Output is correct
7 Correct 17 ms 35928 KB Output is correct
8 Correct 17 ms 35932 KB Output is correct
9 Correct 18 ms 35676 KB Output is correct
10 Correct 21 ms 35672 KB Output is correct
11 Correct 17 ms 35672 KB Output is correct
12 Correct 18 ms 35808 KB Output is correct
13 Correct 19 ms 35928 KB Output is correct
14 Correct 18 ms 35676 KB Output is correct
15 Correct 19 ms 35932 KB Output is correct
16 Correct 19 ms 35944 KB Output is correct
17 Correct 17 ms 35932 KB Output is correct
18 Correct 19 ms 35760 KB Output is correct
19 Correct 39 ms 38740 KB Output is correct
20 Correct 46 ms 38492 KB Output is correct
21 Correct 38 ms 38808 KB Output is correct
22 Correct 33 ms 39004 KB Output is correct
23 Correct 32 ms 38740 KB Output is correct
24 Correct 33 ms 38736 KB Output is correct
25 Correct 34 ms 38484 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35676 KB Output is correct
2 Correct 18 ms 35676 KB Output is correct
3 Correct 17 ms 35928 KB Output is correct
4 Correct 17 ms 35676 KB Output is correct
5 Correct 17 ms 35676 KB Output is correct
6 Correct 16 ms 35932 KB Output is correct
7 Correct 17 ms 35928 KB Output is correct
8 Correct 17 ms 35932 KB Output is correct
9 Correct 18 ms 35676 KB Output is correct
10 Correct 17 ms 35676 KB Output is correct
11 Correct 18 ms 35672 KB Output is correct
12 Correct 20 ms 35676 KB Output is correct
13 Correct 18 ms 35932 KB Output is correct
14 Correct 16 ms 35932 KB Output is correct
15 Correct 18 ms 36152 KB Output is correct
16 Correct 16 ms 35932 KB Output is correct
17 Correct 17 ms 35936 KB Output is correct
18 Correct 17 ms 35676 KB Output is correct
19 Correct 94 ms 52072 KB Output is correct
20 Correct 94 ms 52168 KB Output is correct
21 Runtime error 91 ms 76484 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 52680 KB Output is correct
2 Correct 111 ms 52680 KB Output is correct
3 Correct 130 ms 52676 KB Output is correct
4 Runtime error 100 ms 80464 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35676 KB Output is correct
2 Correct 112 ms 52744 KB Output is correct
3 Correct 121 ms 52676 KB Output is correct
4 Correct 158 ms 52624 KB Output is correct
5 Runtime error 109 ms 76488 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -