oj.uz

Submission #653782

# Submission time Handle Problem Language Result Execution time Memory
653782 2022-10-28T08:01:37 Z atigun Event Hopping (BOI22_events) C++14
30 / 100
 220 ms 64800 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5;

struct interval{
  int L, R;
};

int n, qq;
vector<interval> a(maxn+5);
vector<vector<int>> BL(30, vector<int>(2*maxn+5, -1));


template<typename T>
struct RMQ{
  vector<vector<T>> table;
  int sz, log_sz;
  RMQ(vector<T>& a, int n) : sz(n), log_sz(__lg(n)){
    table.resize(log_sz+5);
    for(int i = 0; i < log_sz+5; i++)
      table[i].resize(n+5, {1e9, 1e9});
    table[0] = a;
    for(int jump = 1; jump <= log_sz; jump++)
      for(int i = 0; i+(1<<(jump-1)) < n; i++)
        table[jump][i] = min(table[jump-1][i], table[jump-1][i+(1<<(jump-1))]);
  }
  T get(int l, int r){
    if(l > r)
      swap(l, r);
    int LogN = __lg(r-l+1);
    return min(table[LogN][l], table[LogN][r-(1<<(LogN))+1]);
  }
};

void compress(){
  vector<int> values(2*n), compressed(2*n);
  for(int i = 0; i < 2*n; i+= 2){
    values[i] = a[i/2].L;
    values[i+1] = a[i/2].R;
  }
  sort(values.begin(), values.end());
  int timer = 0;
  compressed[0] = timer;
  for(int i = 1; i < 2*n; i++){
    if(values[i] == values[i-1]){
      compressed[i] = timer;
    }else{
      compressed[i] = ++timer;
    }
  }
  for(int i = 0; i < n; i++){
    a[i].L = compressed[lower_bound(values.begin(), values.end(), a[i].L)-values.begin()];
    a[i].R = compressed[lower_bound(values.begin(), values.end(), a[i].R)-values.begin()];
  }
}

void solve(){
  cin >> n >> qq;
  for(int i = 0; i < n; i++)
    cin >> a[i].L >> a[i].R;
  compress();
  vector<pair<int, int>> ST_beg(2*maxn+5, {1e9, 1e9});
  for(int i = 0; i < n; i++)
    ST_beg[a[i].R] = min(make_pair(a[i].L, i), ST_beg[a[i].R]);
  RMQ<pair<int, int>> ST(ST_beg, 2*maxn);
  for(int i = 0; i < n; i++){
    pair<int, int> got = ST.get(a[i].L, a[i].R);
    if(got.first < a[i].L){
      BL[0][i] = got.second;
    }else{
      BL[0][i] = -1;
    }
  }
  for(int jump = 1; jump < 30; jump++){
    for(int v = 0; v < n; v++){
      if(BL[jump-1][v] != -1)
        BL[jump][v] = BL[jump-1][BL[jump-1][v]];
    }
  }
  while(qq--){
    int s, e;
    cin >> s >> e;
    s--, e--;
    int k = 0;
    for(int jump = 20; jump >= 0; jump--){
      if(a[e].L <= a[s].R && a[e].R >= a[s].R)
        break;
      assert(e < n);
      assert(e >= 0);
      if(BL[jump][e] != -1 && a[BL[jump][e]].R >= a[s].R){
        k+= (1<<jump);
        e = BL[jump][e];
      }
    }
    if(s == e){
      cout << k << "\n";
    }else if(a[e].R >= a[s].R && a[e].L <= a[s].R){
      cout << k+1 << "\n";
    }else{
      cout << "impossible\n";
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while(tt--){
    solve();
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 60604 KB Output is correct
2 Correct 147 ms 64552 KB Output is correct
3 Correct 157 ms 63956 KB Output is correct
4 Correct 220 ms 63888 KB Output is correct
5 Correct 154 ms 63916 KB Output is correct
6 Correct 169 ms 63940 KB Output is correct
7 Correct 172 ms 63980 KB Output is correct
8 Correct 135 ms 64288 KB Output is correct
9 Correct 138 ms 64500 KB Output is correct
10 Correct 186 ms 64344 KB Output is correct
11 Correct 191 ms 64292 KB Output is correct
12 Correct 96 ms 64284 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 60608 KB Output is correct
2 Correct 36 ms 60704 KB Output is correct
3 Correct 31 ms 60740 KB Output is correct
4 Correct 31 ms 60740 KB Output is correct
5 Correct 32 ms 60644 KB Output is correct
6 Incorrect 42 ms 60656 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 60608 KB Output is correct
2 Correct 36 ms 60704 KB Output is correct
3 Correct 31 ms 60740 KB Output is correct
4 Correct 31 ms 60740 KB Output is correct
5 Correct 32 ms 60644 KB Output is correct
6 Incorrect 42 ms 60656 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 60608 KB Output is correct
2 Correct 36 ms 60704 KB Output is correct
3 Correct 31 ms 60740 KB Output is correct
4 Correct 31 ms 60740 KB Output is correct
5 Correct 32 ms 60644 KB Output is correct
6 Incorrect 42 ms 60656 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 64592 KB Output is correct
2 Correct 140 ms 63644 KB Output is correct
3 Correct 194 ms 63724 KB Output is correct
4 Correct 130 ms 64148 KB Output is correct
5 Correct 206 ms 64032 KB Output is correct
6 Correct 189 ms 63792 KB Output is correct
7 Correct 154 ms 64648 KB Output is correct
8 Correct 156 ms 64800 KB Output is correct
9 Correct 107 ms 62752 KB Output is correct
10 Correct 139 ms 64300 KB Output is correct
11 Correct 149 ms 64044 KB Output is correct
12 Correct 154 ms 64320 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 60604 KB Output is correct
2 Correct 147 ms 64552 KB Output is correct
3 Correct 157 ms 63956 KB Output is correct
4 Correct 220 ms 63888 KB Output is correct
5 Correct 154 ms 63916 KB Output is correct
6 Correct 169 ms 63940 KB Output is correct
7 Correct 172 ms 63980 KB Output is correct
8 Correct 135 ms 64288 KB Output is correct
9 Correct 138 ms 64500 KB Output is correct
10 Correct 186 ms 64344 KB Output is correct
11 Correct 191 ms 64292 KB Output is correct
12 Correct 96 ms 64284 KB Output is correct
13 Correct 31 ms 60608 KB Output is correct
14 Correct 36 ms 60704 KB Output is correct
15 Correct 31 ms 60740 KB Output is correct
16 Correct 31 ms 60740 KB Output is correct
17 Correct 32 ms 60644 KB Output is correct
18 Incorrect 42 ms 60656 KB Output isn't correct
19 Halted 0 ms 0 KB -