Submission #900036

#	Time	Username	Problem	Language	Result	Execution time	Memory
900036		duckindog	Osumnjičeni (COCI21_osumnjiceni)	C++14	0 / 110	828 ms	40752 KiB

Main

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

using namespace std;

const int N = 2e5 + 10;
struct Q{
  int p = 0, q = 0, id = 0;
} que[N];
int answer[N];

int n;
int l[N], r[N];
int m;

int f[4 * N], lazy[4 * N];
void push(int s) {
  if (!lazy[s]) return;

  f[s * 2] += lazy[s];    f[s * 2 + 1] += lazy[s];
  lazy[s * 2] += lazy[s]; lazy[s * 2 + 1] += lazy[s];

  lazy[s] = 0;
}
void update(int s, int l, int r, int u, int v, int x) {
  if (v < l || u > r) return;
  if (u <= l && r <= v) {
    f[s] += x;
    lazy[s] += x;
    return;
  }
  push(s);
  int mid = l + r >> 1;
  update(s * 2, l, mid, u, v, x); update(s * 2 + 1, mid + 1, r, u, v, x);
  f[s] = max(f[s * 2], f[s * 2 + 1]);
}
int query(int s, int l, int r, int u, int v) {
  if (v < l || u > r) return 0;
  if (u <= l && r <= v) return f[s];
  push(s);
  int mid = l + r >> 1;
  return max(query(s * 2, l, mid, u, v), query(s * 2 + 1, mid + 1, r, u, v));
}

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;

  vector<int> rrh;
  map<int, int> rvs;
  for (int i = 1; i <= n; ++i) {
    cin >> l[i] >> r[i];
    rrh.push_back(l[i]);
    rrh.push_back(r[i]);
  }

  //rrh
  sort(rrh.begin(), rrh.end());
  rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());
  int sz = rrh.size();
  for (int i = 0; i < sz; ++i) rvs[rrh[i]] = i + 1;
  //end rrh

  cin >> m;
  for (int i = 1; i <= m; ++i) {
    int p, q; cin >> p >> q;
    que[i] = {p, q, i};
  }

  sort(que + 1, que + m + 1, [&] (Q a, Q b){
    if (a.p == b.p) return a.q < b.q;
    return a.p < b.p;
  });

  int lt = 0, rt = 0;
  for (int i = 1; i <= m; ++i) {
    int p = que[i].p, q = que[i].q, id = que[i].id;

    while (lt < p) {
      update(1, 1, sz, rvs[l[lt]], rvs[r[lt]], -1);
      lt += 1;
    }

    while (rt <= q) {
      update(1, 1, sz, rvs[l[rt]], rvs[r[rt]], 1);
      rt += 1;
    }

    answer[id] = query(1, 1, sz, 1, sz);

  }

  for (int i = 1; i <= m; ++i) cout << answer[i] << '\n';

}

Compilation message (stderr)

Main.cpp: In function 'void update(int, int, int, int, int, int)':
Main.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int query(int, int, int, int, int)':
Main.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int32_t main()':
Main.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:50:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     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