Submission #901187

#	Time	Username	Problem	Language	Result	Execution time	Memory
901187		duckindog	Osumnjičeni (COCI21_osumnjiceni)	C++14	0 / 110	55 ms	20652 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) {
  return x.second < y.first || x.first > y.second;
}

void init() {

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

    while (j <= n) {
      pii now = {lt[j], rt[j]};
      auto it = duck.upper_bound(now);
      if (!duck.size()) {
        duck.insert(now);
        j += 1;
      }
      else {
        it--;
        if (chk(*it, now)) {
          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:61:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:62:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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