oj.uz

답안 #653891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653891 2022-10-28T18:15:43 Z atigun Event Hopping (BOI22_events) C++14
30 / 100
 189 ms 63172 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;
  }
  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--;
    if(s != e && a[s].L == a[e].L && a[s].R == a[e].R){
      cout << 1 << "\n";
      continue;
    }
    int k = 0;
    for(int jump = 20; jump >= 0; jump--){
      if(a[e].L <= a[s].R && a[e].R >= a[s].R)
        break;
      if(BL[jump][e] != -1 && a[BL[jump][e]].R >= a[s].R){
        k+= (1<<jump);
        e = BL[jump][e];
      }
    }
    if(a[e].R == a[s].R && a[e].L == a[s].L){
      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

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 60604 KB Output is correct
2 Correct 121 ms 62984 KB Output is correct
3 Correct 142 ms 62500 KB Output is correct
4 Correct 189 ms 62644 KB Output is correct
5 Correct 142 ms 62652 KB Output is correct
6 Correct 144 ms 62664 KB Output is correct
7 Correct 143 ms 62748 KB Output is correct
8 Correct 120 ms 63136 KB Output is correct
9 Correct 124 ms 63120 KB Output is correct
10 Correct 162 ms 63132 KB Output is correct
11 Correct 150 ms 63132 KB Output is correct
12 Correct 83 ms 63008 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 60720 KB Output is correct
2 Correct 30 ms 60652 KB Output is correct
3 Correct 32 ms 60656 KB Output is correct
4 Correct 30 ms 60740 KB Output is correct
5 Correct 30 ms 60648 KB Output is correct
6 Incorrect 31 ms 60724 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 60720 KB Output is correct
2 Correct 30 ms 60652 KB Output is correct
3 Correct 32 ms 60656 KB Output is correct
4 Correct 30 ms 60740 KB Output is correct
5 Correct 30 ms 60648 KB Output is correct
6 Incorrect 31 ms 60724 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 60720 KB Output is correct
2 Correct 30 ms 60652 KB Output is correct
3 Correct 32 ms 60656 KB Output is correct
4 Correct 30 ms 60740 KB Output is correct
5 Correct 30 ms 60648 KB Output is correct
6 Incorrect 31 ms 60724 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 62896 KB Output is correct
2 Correct 152 ms 62580 KB Output is correct
3 Correct 186 ms 62332 KB Output is correct
4 Correct 121 ms 62876 KB Output is correct
5 Correct 161 ms 62796 KB Output is correct
6 Correct 172 ms 62600 KB Output is correct
7 Correct 170 ms 63032 KB Output is correct
8 Correct 163 ms 63172 KB Output is correct
9 Correct 92 ms 61492 KB Output is correct
10 Correct 139 ms 62752 KB Output is correct
11 Correct 130 ms 62540 KB Output is correct
12 Correct 137 ms 62668 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 60604 KB Output is correct
2 Correct 121 ms 62984 KB Output is correct
3 Correct 142 ms 62500 KB Output is correct
4 Correct 189 ms 62644 KB Output is correct
5 Correct 142 ms 62652 KB Output is correct
6 Correct 144 ms 62664 KB Output is correct
7 Correct 143 ms 62748 KB Output is correct
8 Correct 120 ms 63136 KB Output is correct
9 Correct 124 ms 63120 KB Output is correct
10 Correct 162 ms 63132 KB Output is correct
11 Correct 150 ms 63132 KB Output is correct
12 Correct 83 ms 63008 KB Output is correct
13 Correct 31 ms 60720 KB Output is correct
14 Correct 30 ms 60652 KB Output is correct
15 Correct 32 ms 60656 KB Output is correct
16 Correct 30 ms 60740 KB Output is correct
17 Correct 30 ms 60648 KB Output is correct
18 Incorrect 31 ms 60724 KB Output isn't correct
19 Halted 0 ms 0 KB -