Submission #1202355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202355		zNatsumi	Osumnjičeni (COCI21_osumnjiceni)	C++20	0 / 110	1093 ms	700 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

const int RANDOM = chrono::steady_clock::now().time_since_epoch().count();
struct chash{ int operator()(int x){ return x ^ RANDOM; } };

using ii = pair<int, int>;

const int N = 5e3 + 5;

int n, q, l[N], r[N], ri[N];
vector<int> rrh;

namespace IT{
  bool st[N<<3], lz[N<<3];

  void build(int tl, int tr, int i){
    st[i] = lz[i] = 0;
    if(tl == tr) return;
    int tm = tl + tr >> 1;
    build(tl, tm, i<<1);
    build(tm + 1, tr, i<<1|1);
  }

  void push(int i){
    if(!lz[i]) return;
    st[i<<1] |= lz[i];  st[i<<1|1] |= lz[i];
    lz[i<<1] |= lz[i];  lz[i<<1|1] |= lz[i];  lz[i] = 0;
  }

  void update(int l, int r, int tl, int tr, int i){
    if(r < tl || tr < l || l > r) return;
    if(l <= tl && tr <= r){
      st[i] = 1;
      lz[i] = 1;
      return;
    }
    push(i);
    int tm = tl + tr >> 1;
    update(l, r, tl, tm, i<<1);
    update(l, r, tm + 1, tr, i<<1|1);
    st[i] = st[i<<1] | st[i<<1|1];
  }
  bool get(int l, int r, int tl, int tr, int i){
    if(r < tl || tr < l || l > r) return 0;
    if(l <= tl && tr <= r) return st[i];
    push(i);
    int tm = tl + tr >> 1;
    return get(l, r, tl, tm, i<<1) | get(l, r, tm + 1, tr, i<<1|1);
  }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
  for(int i = 1; i <= n; i++){
    rrh.push_back(l[i]);
    rrh.push_back(r[i]);
  }
  sort(rrh.begin(), rrh.end());
  rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end());
  for(int i = 1; i <= n; i++){
    l[i] = lower_bound(rrh.begin(), rrh.end(), l[i]) - rrh.begin() + 1;
    r[i] = lower_bound(rrh.begin(), rrh.end(), r[i]) - rrh.begin() + 1;
  }
  int lim = rrh.size();

  for(int i = 1; i <= n; i++){
    IT::build(1, lim, 1);
    for(int j = i; j <= n; j++){
      if(IT::get(l[j], r[j], 1, lim, 1)) break;
      IT::update(l[j], r[j], 1, lim, 1);
      ri[i] = j;
    }
  }

  cin >> q;
  while(q--){
    int u, v; cin >> u >> v;

    int res = 0;
    while(u <= v){
      res += 1;
      u = ri[u] + 1;
    }
    cout << res << "\n";
  }

  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50