Submission #61826772

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
/*
  [5, 7, 3, 4]
*/
class fenTree {
  int n;
  vector <i64> tree;
public:
  fenTree(int n) {
    this -> n = n;
    tree.resize(n + 1);
  }
  void upd(int pos, int del) {
    for (int i = pos; i <= n; i += i & -i) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

/*
  [5, 7, 3, 4]

*/


class fenTree {
  int n;
  vector <i64> tree;
public:
  fenTree(int n) {
    this -> n = n;
    tree.resize(n + 1);
  }
  void upd(int pos, int del) {
    for (int i = pos; i <= n; i += i & -i) {
      tree[i] += del;
    }
  }
  i64 qry(int r) {
    i64 res = 0;
    for (int i = r; i >= 1; i -= i & -i) {
      res += tree[i];
    }
    return res;
  }
  i64 range(int l, int r) {
    return qry(r) - qry(l - 1);
  }
};

const int N = 5e5;

void solve() {
  int n;
  cin >> n;

  vector <array <int, 2>> a (n);
  for (int i = 0; i < n; ++i) {
    auto &[x, y] = a[i];
    cin >> x >> y;
  }

  fenTree tree(N + 5);
  for (int i = 1; i <= N; ++i) {
    tree.upd(i, i);
    tree.upd(i + 1, -i);
  }

  auto pr = [&] () -> void {
    for (int i = 1; i <= n; ++i) {
      cout << tree.qry(i) << ' ';
    }
    cout << '\n';
  };

  // pr();

  for (int i = 0; i < n; ++i) {
    auto [x, y] = a[i];
    int L = N + 1, R = 0;
    int lo = 0, hi = N + 1;
    while (hi - lo > 1) {
      int mid = (lo + hi) >> 1;
      int at = tree.qry(mid);
      if (at >= x) hi = mid;
      else lo = mid;
    }
    L = hi;

    lo = 0, hi = N + 1;
    while (hi - lo > 1) {
      int mid = (lo + hi) >> 1;
      int at = tree.qry(mid);
      if (at <= y) lo = mid;
      else hi = mid;
    }
    R = lo;

    if (L <= R) {
      tree.upd(L, 1);
      tree.upd(R + 1, -1);
    }
    // pr();
  }

  int q;
  cin >> q;
  while(q--) {
    int x;
    cin >> x;

    int ans = tree.qry(x);
    cout << ans << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(0);
  int tests = 1;
  // cin >> tests;
  for (int test = 0; test < tests; ++test) {
    solve();
  }
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:55:8: warning: variable ‘pr’ set but not used [-Wunused-but-set-variable]
   55 |   auto pr = [&] () -> void {
      |        ^~

Judge Result