oj.uz

Submission #1023779

# Submission time Handle Problem Language Result Execution time Memory
1023779 2024-07-15T06:25:36 Z vjudge1 Osumnjičeni (COCI21_osumnjiceni) C++17
0 / 110
 117 ms 21300 KB 
#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 && r <= it->first) {return false;}
  if(it != st.begin())
    {
      it--;
      if(l <= it->first && it->first <= r) {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; i + (1 << l) <= n; 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(a + (1 << i) <= n && par[a][i] < b) ans += (1 << i), a = par[a][i];
      cout << ans + 1 << endl;
    }
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 20560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 21300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 20560 KB Output isn't correct
2 Halted 0 ms 0 KB -