Submission #1023780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023780		vjudge1	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	523 ms	33212 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N = 200'000 + 50, K = 20;
int n, q, l[N], r[N], par[N][K];
set<pair<int, int> > st;

bool check(int l, int r)
{
  if(st.empty()) return true;

  auto it = st.upper_bound({r, 0});
  if(it != st.end() && it->second <= r) return false;
  if(it != st.begin())
    {
      it--;
      if(l <= it->first) return false;
    }
  return true;
}

int main()
{
  cin >> n;
  for(int i = 0; i < n; i ++)
    cin >> l[i] >> r[i];

  int j = 0;
  for(int i = 0; i < n; i ++)
    {
      while(j < n && check(l[j], r[j]))
	st.insert({r[j], l[j]}), j++;
      par[i][0] = j;
      st.erase({r[i], l[i]});
    }

  for(int i = K - 1; i >= 0; i --) par[n][i] = n;
  
  for(int i = n - 1; i >= 0; i --)
    for(int l = 1; l < K; l++)
      par[i][l] = par[par[i][l - 1]][l -1];
		     
  // cerr << par[0][0] << endl;
  cin >> q;
  while(q--)
    {
      int a, b;
      cin >> a >> b;
      a--;
      int ans = 0;
      for(int i = K - 1; i >= 0; i --)
	if(par[a][i] < b) ans += (1 << i), a = par[a][i];
      cout << ans + 1 << endl;
    }
  return 0;
}

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