oj.uz

Submission #1009440

# Submission time Handle Problem Language Result Execution time Memory
1009440 2024-06-27T14:07:31 Z mispertion Event Hopping (BOI22_events) C++17
25 / 100
 127 ms 78284 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;
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 33628 KB Output is correct
2 Correct 113 ms 46432 KB Output is correct
3 Correct 121 ms 46568 KB Output is correct
4 Correct 127 ms 46340 KB Output is correct
5 Runtime error 88 ms 74028 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 33820 KB Output is correct
2 Correct 19 ms 33624 KB Output is correct
3 Correct 18 ms 33880 KB Output is correct
4 Correct 18 ms 33884 KB Output is correct
5 Correct 22 ms 33880 KB Output is correct
6 Correct 20 ms 33704 KB Output is correct
7 Correct 18 ms 33884 KB Output is correct
8 Correct 20 ms 33884 KB Output is correct
9 Correct 23 ms 33884 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 33820 KB Output is correct
2 Correct 19 ms 33624 KB Output is correct
3 Correct 18 ms 33880 KB Output is correct
4 Correct 18 ms 33884 KB Output is correct
5 Correct 22 ms 33880 KB Output is correct
6 Correct 20 ms 33704 KB Output is correct
7 Correct 18 ms 33884 KB Output is correct
8 Correct 20 ms 33884 KB Output is correct
9 Correct 23 ms 33884 KB Output is correct
10 Correct 19 ms 33796 KB Output is correct
11 Correct 18 ms 33628 KB Output is correct
12 Correct 24 ms 33744 KB Output is correct
13 Correct 23 ms 33880 KB Output is correct
14 Correct 20 ms 33884 KB Output is correct
15 Correct 20 ms 33652 KB Output is correct
16 Correct 21 ms 33780 KB Output is correct
17 Correct 18 ms 33884 KB Output is correct
18 Correct 19 ms 33628 KB Output is correct
19 Correct 42 ms 35412 KB Output is correct
20 Correct 39 ms 35432 KB Output is correct
21 Correct 41 ms 35736 KB Output is correct
22 Correct 37 ms 35668 KB Output is correct
23 Correct 40 ms 35668 KB Output is correct
24 Correct 34 ms 35752 KB Output is correct
25 Correct 47 ms 35412 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 33820 KB Output is correct
2 Correct 19 ms 33624 KB Output is correct
3 Correct 18 ms 33880 KB Output is correct
4 Correct 18 ms 33884 KB Output is correct
5 Correct 22 ms 33880 KB Output is correct
6 Correct 20 ms 33704 KB Output is correct
7 Correct 18 ms 33884 KB Output is correct
8 Correct 20 ms 33884 KB Output is correct
9 Correct 23 ms 33884 KB Output is correct
10 Correct 18 ms 33628 KB Output is correct
11 Correct 19 ms 33664 KB Output is correct
12 Correct 19 ms 33884 KB Output is correct
13 Correct 20 ms 33884 KB Output is correct
14 Correct 19 ms 33884 KB Output is correct
15 Correct 19 ms 33880 KB Output is correct
16 Correct 19 ms 33920 KB Output is correct
17 Correct 19 ms 33880 KB Output is correct
18 Correct 19 ms 33884 KB Output is correct
19 Correct 95 ms 44668 KB Output is correct
20 Correct 91 ms 43980 KB Output is correct
21 Runtime error 107 ms 73744 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 121 ms 46420 KB Output is correct
2 Correct 119 ms 46540 KB Output is correct
3 Correct 125 ms 46540 KB Output is correct
4 Runtime error 119 ms 78284 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 33628 KB Output is correct
2 Correct 113 ms 46432 KB Output is correct
3 Correct 121 ms 46568 KB Output is correct
4 Correct 127 ms 46340 KB Output is correct
5 Runtime error 88 ms 74028 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -