oj.uz

Submission #660548

# Submission time Handle Problem Language Result Execution time Memory
660548 2022-11-22T08:49:29 Z mychecksedad Event Hopping (BOI22_events) C++17
0 / 100
 182 ms 16252 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 == i ? -1 : p);
    }
    for(int j = 1; j < K; ++j) for(int i = 1; i <= n; ++i){
        int next = up[i][j - 1];
        if(next == -1)
            up[i][j] = -1;
        else
            up[i][j] = up[next][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{
            int v = a[start][2], ans = 0;
            for(int j = K - 1; j >= 0; --j){
                if(up[v][j] != -1 && 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);
            // cout << b[last][0] << ' ' << b[last][1] << '\n';
            // cout << b[v][0] << ' ' << b[v][1] << '\n';
            if(last == MOD || b[last][1] > a[end][1] || b[last][1] < a[end][0]) 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:124:16: warning: unused variable 'aa' [-Wunused-variable]
  124 |     int T = 1, aa;
      |                ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 153 ms 16128 KB Output is correct
3 Correct 156 ms 16124 KB Output is correct
4 Incorrect 169 ms 16252 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 16028 KB Output is correct
2 Correct 182 ms 16100 KB Output is correct
3 Incorrect 168 ms 16176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 153 ms 16128 KB Output is correct
3 Correct 156 ms 16124 KB Output is correct
4 Incorrect 169 ms 16252 KB Output isn't correct
5 Halted 0 ms 0 KB -