Submission #901241

#	Time	Username	Problem	Language	Result	Execution time	Memory
901241		duckindog	Osumnjičeni (COCI21_osumnjiceni)	C++14	110 / 110	224 ms	32336 KiB

Main

//from duckindog wth depressiong
#include<bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
const int N = 2e5 + 10;
int n;
int lt[N], rt[N];

int f[N][19];
bool chk(pii x, pii y) {
  bool pass = 0;
  for (int i = 0; i < 2; ++i) {
    pass |= (x.second < y.first || x.first > y.second) ;
    swap(x, y);
  }
  return pass;
}

void init() {

  set<pii> duck;
  int j = 1;
  for (int i = 1; i <= n; ++i) {
    duck.erase({lt[i - 1], rt[i - 1]});

    if (j < i) {
      duck.clear();
      j = i;
    }

    while (j <= n) {
      pii now = {lt[j], rt[j]};
      auto it = duck.lower_bound(now);
      bool pass = chk(*it, now);

      if (it != duck.begin()) it--;
      pass &= chk(*it, now);
      if (pass) {
        duck.insert(now);
        j += 1;
      } else break;

    }

    f[i][0] = j;

  }
  for (int j = 1; j <= 18; ++j) {
    for (int i = 1; i <= n; ++i) {
      f[i][j] = f[f[i][j - 1]][j - 1];
    }
  }

}
int get(int l, int r) {
  int answer = 0;
  for (int i = 18; i >= 0; --i) {
    if (!f[l][i] || f[l][i] > r) continue;
    l = f[l][i];
    answer += 1 << i;
  }
  return answer + 1;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> lt[i] >> rt[i];
  init();

  int m; cin >> m;
  while (m--) {
    int p, q; cin >> p >> q;
    cout << get(p, q) << '\n';
  }

}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:72:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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