oj.uz

Submission #853859

# Submission time Handle Problem Language Result Execution time Memory
853859 2023-09-25T10:33:00 Z mychecksedad Event Hopping (BOI22_events) C++17
30 / 100
 166 ms 28120 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] && a[start][0] <= a[end][1]) 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:121:16: warning: unused variable 'aa' [-Wunused-variable]
  121 |     int T = 1, aa;
      |                ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 127 ms 24524 KB Output is correct
3 Correct 135 ms 24524 KB Output is correct
4 Correct 142 ms 24608 KB Output is correct
5 Correct 132 ms 24780 KB Output is correct
6 Correct 135 ms 24608 KB Output is correct
7 Correct 139 ms 24776 KB Output is correct
8 Correct 127 ms 25204 KB Output is correct
9 Correct 126 ms 25124 KB Output is correct
10 Correct 131 ms 24924 KB Output is correct
11 Correct 133 ms 28120 KB Output is correct
12 Correct 92 ms 27340 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 2 ms 6488 KB Output is correct
5 Incorrect 2 ms 6488 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 126 ms 24524 KB Output is correct
2 Correct 128 ms 24552 KB Output is correct
3 Correct 139 ms 24520 KB Output is correct
4 Correct 125 ms 25036 KB Output is correct
5 Correct 128 ms 25032 KB Output is correct
6 Correct 150 ms 27852 KB Output is correct
7 Correct 166 ms 27840 KB Output is correct
8 Correct 143 ms 27852 KB Output is correct
9 Correct 123 ms 25800 KB Output is correct
10 Correct 147 ms 27536 KB Output is correct
11 Correct 156 ms 27336 KB Output is correct
12 Correct 153 ms 27592 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 127 ms 24524 KB Output is correct
3 Correct 135 ms 24524 KB Output is correct
4 Correct 142 ms 24608 KB Output is correct
5 Correct 132 ms 24780 KB Output is correct
6 Correct 135 ms 24608 KB Output is correct
7 Correct 139 ms 24776 KB Output is correct
8 Correct 127 ms 25204 KB Output is correct
9 Correct 126 ms 25124 KB Output is correct
10 Correct 131 ms 24924 KB Output is correct
11 Correct 133 ms 28120 KB Output is correct
12 Correct 92 ms 27340 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6488 KB Output is correct
15 Correct 2 ms 6488 KB Output is correct
16 Correct 2 ms 6488 KB Output is correct
17 Incorrect 2 ms 6488 KB Output isn't correct
18 Halted 0 ms 0 KB -