oj.uz

Submission #653789

# Submission time Handle Problem Language Result Execution time Memory
653789 2022-10-28T09:08:09 Z atigun Event Hopping (BOI22_events) C++14
30 / 100
 194 ms 61924 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--;
    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

# Verdict Execution time Memory Grader output
1 Correct 33 ms 60676 KB Output is correct
2 Correct 115 ms 61456 KB Output is correct
3 Correct 132 ms 61372 KB Output is correct
4 Correct 194 ms 61324 KB Output is correct
5 Correct 135 ms 61468 KB Output is correct
6 Correct 138 ms 61548 KB Output is correct
7 Correct 134 ms 61508 KB Output is correct
8 Correct 113 ms 61912 KB Output is correct
9 Correct 113 ms 61924 KB Output is correct
10 Correct 163 ms 61788 KB Output is correct
11 Correct 150 ms 61788 KB Output is correct
12 Correct 81 ms 61880 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 60604 KB Output is correct
2 Correct 32 ms 60612 KB Output is correct
3 Correct 30 ms 60604 KB Output is correct
4 Correct 32 ms 60696 KB Output is correct
5 Correct 31 ms 60724 KB Output is correct
6 Incorrect 31 ms 60772 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 60604 KB Output is correct
2 Correct 32 ms 60612 KB Output is correct
3 Correct 30 ms 60604 KB Output is correct
4 Correct 32 ms 60696 KB Output is correct
5 Correct 31 ms 60724 KB Output is correct
6 Incorrect 31 ms 60772 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 60604 KB Output is correct
2 Correct 32 ms 60612 KB Output is correct
3 Correct 30 ms 60604 KB Output is correct
4 Correct 32 ms 60696 KB Output is correct
5 Correct 31 ms 60724 KB Output is correct
6 Incorrect 31 ms 60772 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 120 ms 61336 KB Output is correct
2 Correct 140 ms 61396 KB Output is correct
3 Correct 186 ms 61388 KB Output is correct
4 Correct 119 ms 61912 KB Output is correct
5 Correct 161 ms 61732 KB Output is correct
6 Correct 150 ms 61472 KB Output is correct
7 Correct 150 ms 61544 KB Output is correct
8 Correct 152 ms 61728 KB Output is correct
9 Correct 92 ms 60764 KB Output is correct
10 Correct 137 ms 61224 KB Output is correct
11 Correct 138 ms 60956 KB Output is correct
12 Correct 133 ms 61200 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 60676 KB Output is correct
2 Correct 115 ms 61456 KB Output is correct
3 Correct 132 ms 61372 KB Output is correct
4 Correct 194 ms 61324 KB Output is correct
5 Correct 135 ms 61468 KB Output is correct
6 Correct 138 ms 61548 KB Output is correct
7 Correct 134 ms 61508 KB Output is correct
8 Correct 113 ms 61912 KB Output is correct
9 Correct 113 ms 61924 KB Output is correct
10 Correct 163 ms 61788 KB Output is correct
11 Correct 150 ms 61788 KB Output is correct
12 Correct 81 ms 61880 KB Output is correct
13 Correct 30 ms 60604 KB Output is correct
14 Correct 32 ms 60612 KB Output is correct
15 Correct 30 ms 60604 KB Output is correct
16 Correct 32 ms 60696 KB Output is correct
17 Correct 31 ms 60724 KB Output is correct
18 Incorrect 31 ms 60772 KB Output isn't correct
19 Halted 0 ms 0 KB -