oj.uz

Submission #660550

# Submission time Handle Problem Language Result Execution time Memory
660550 2022-11-22T08:52:29 Z mychecksedad Event Hopping (BOI22_events) C++17
10 / 100
 213 ms 17676 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 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] != -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);
            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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 161 ms 16132 KB Output is correct
3 Correct 159 ms 16128 KB Output is correct
4 Correct 163 ms 16132 KB Output is correct
5 Correct 165 ms 17220 KB Output is correct
6 Correct 163 ms 17224 KB Output is correct
7 Correct 161 ms 17176 KB Output is correct
8 Correct 161 ms 17608 KB Output is correct
9 Correct 153 ms 17672 KB Output is correct
10 Correct 176 ms 17528 KB Output is correct
11 Correct 194 ms 17468 KB Output is correct
12 Correct 124 ms 17608 KB Output is correct

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 162 ms 16036 KB Output is correct
2 Correct 168 ms 16032 KB Output is correct
3 Correct 162 ms 16044 KB Output is correct
4 Correct 163 ms 17676 KB Output is correct
5 Correct 213 ms 17488 KB Output is correct
6 Incorrect 203 ms 17552 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 161 ms 16132 KB Output is correct
3 Correct 159 ms 16128 KB Output is correct
4 Correct 163 ms 16132 KB Output is correct
5 Correct 165 ms 17220 KB Output is correct
6 Correct 163 ms 17224 KB Output is correct
7 Correct 161 ms 17176 KB Output is correct
8 Correct 161 ms 17608 KB Output is correct
9 Correct 153 ms 17672 KB Output is correct
10 Correct 176 ms 17528 KB Output is correct
11 Correct 194 ms 17468 KB Output is correct
12 Correct 124 ms 17608 KB Output is correct
13 Incorrect 0 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -