oj.uz

Submission #660551

# Submission time Handle Problem Language Result Execution time Memory
660551 2022-11-22T09:01:49 Z mychecksedad Event Hopping (BOI22_events) C++17
30 / 100
 203 ms 17528 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD1 (1000000000+7)
#define MOD (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;


int n, q, t[N][2], up[N][K];
array<int, 3> a[N], b[N]; // original, sorted by r;
vector<int> all;

void build(int l, int r, int k){
    if(l==r){
        t[k][0] = MOD;
        t[k][1] = 0;
        return;
    }
    int m = (l+r)>>1;
    build(l, m, k<<1);
    build(m+1, r, k<<1|1);
    t[k][0] = MOD;
    t[k][1] = 0;
}
int get(int l, int r, int p, int k, bool f){
    if(p > r || l > p) return (f ? 0 : MOD);
    if(l == r) return t[k][f];
    int m = (l+r)>>1;
    if(f)
        return max({t[k][f], get(l, m, p, k<<1, f), get(m+1, r, p, k<<1|1, f)});
    else
        return min({t[k][f], get(l, m, p, k<<1, f), get(m+1, r, p, k<<1|1, f)});
}

void update(int l, int r, int ql, int qr, int k, int val, bool f){
    if(ql > r || l > qr) return;
    if(ql <= l && r <= qr){
        if(f)
            t[k][f] = max(val, t[k][f]);
        else
            t[k][f] = min(val, t[k][f]);
        return;
    }
    int m = (l+r)>>1;
    update(l, m, ql, qr, k<<1, val, f);
    update(m+1, r, ql, qr, k<<1|1, val, f);
}

bool comp(const array<int, 3> &a, const array<int, 3> &b){
    if(a[1] != b[1])
        return a[1] < b[1];
    return a[0] < b[0];
}

void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        cin >> a[i][0] >> a[i][1];
        all.pb(a[i][0]);
        all.pb(a[i][1]);
        a[i][2] = i;
    }
    
    sort(all(all));
    unique(all(all));
    build(1, 2*n, 1);

    for(int i = 1; i <= n; ++i){
        a[i][0] = lower_bound(all(all), a[i][0]) - all.begin() + 1;
        a[i][1] = lower_bound(all(all), a[i][1]) - all.begin() + 1;
        b[i] = a[i];
    }

    sort(b + 1, b + 1 + n, comp);

    for(int i = 1; i <= n; ++i){
        update(1, 2*n, b[i][0], b[i][1], 1, i, 1);
        if(b[i][0] != b[i][1])
            update(1, 2*n, b[i][0], b[i][1] - 1, 1, i, 0);
        a[b[i][2]][2] = i;
    }
    for(int i = 1; i <= n; ++i){
        int p = get(1, 2*n, b[i][1], 1, 1);
        up[i][0] = p;
    }
    for(int j = 1; j < K; ++j) for(int i = 1; i <= n; ++i) up[i][j] = up[up[i][j - 1]][j - 1];
    for(;q--;){
        int start, end; cin >> start >> end;
        if(start == end) cout << "0\n";
        else if(a[start][1] > a[end][1]) cout << "impossible\n";
        else if(a[start][1] >= a[end][0]) cout << "1\n";
        else{
            int v = a[start][2], ans = 0;
            for(int j = K - 1; j >= 0; --j){
                if(up[v][j] == v) break;
                if(b[up[v][j]][1] < a[end][0]) v = up[v][j], ans += (1<<j);
            }
            int last = get(1, 2*n, b[v][1], 1, 0);
            if(last == MOD || b[last][1] > a[end][1]) cout << "impossible\n";
            else cout << ans + 2 << '\n';
        }
    }
}




int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
    }
    return 0;
 
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:119:16: warning: unused variable 'aa' [-Wunused-variable]
  119 |     int T = 1, aa;
      |                ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 155 ms 16124 KB Output is correct
3 Correct 156 ms 16072 KB Output is correct
4 Correct 165 ms 16128 KB Output is correct
5 Correct 164 ms 16264 KB Output is correct
6 Correct 163 ms 16164 KB Output is correct
7 Correct 158 ms 16144 KB Output is correct
8 Correct 150 ms 16568 KB Output is correct
9 Correct 152 ms 16644 KB Output is correct
10 Correct 169 ms 16504 KB Output is correct
11 Correct 169 ms 16496 KB Output is correct
12 Correct 121 ms 16564 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 16144 KB Output is correct
2 Correct 177 ms 16096 KB Output is correct
3 Correct 167 ms 16080 KB Output is correct
4 Correct 153 ms 16564 KB Output is correct
5 Correct 191 ms 16496 KB Output is correct
6 Correct 200 ms 16260 KB Output is correct
7 Correct 203 ms 17224 KB Output is correct
8 Correct 186 ms 17528 KB Output is correct
9 Correct 150 ms 16468 KB Output is correct
10 Correct 176 ms 16848 KB Output is correct
11 Correct 183 ms 16720 KB Output is correct
12 Correct 189 ms 16952 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 155 ms 16124 KB Output is correct
3 Correct 156 ms 16072 KB Output is correct
4 Correct 165 ms 16128 KB Output is correct
5 Correct 164 ms 16264 KB Output is correct
6 Correct 163 ms 16164 KB Output is correct
7 Correct 158 ms 16144 KB Output is correct
8 Correct 150 ms 16568 KB Output is correct
9 Correct 152 ms 16644 KB Output is correct
10 Correct 169 ms 16504 KB Output is correct
11 Correct 169 ms 16496 KB Output is correct
12 Correct 121 ms 16564 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Incorrect 1 ms 468 KB Output isn't correct
18 Halted 0 ms 0 KB -