Submission #1184637

#TimeUsernameProblemLanguageResultExecution timeMemory
1184637mannshah1211Examination (JOI19_examination)C++17
0 / 100
236 ms7912 KiB
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "deb.h"
#else
#define debug(...) 
#endif

#define pb emplace_back
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < n; i++) 
#define per(i, n) for (int i = n - 1; i >= 0; i--) 
#define sz(a) (int) (a).size()
#define f first
#define s second

using vi = vector<int>;
using ll = long long;

template <typename T>
class fenwick {
 public:
  map<T, T> fenw;
  int n;

  fenwick(int _n) : n(_n) {
    
  }

  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }

  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

void solve() {
  int n, q;
  cin >> n >> q;
  vector<pair<int, int>> a(n);
  rep(i, n) {
    cin >> a[i].f >> a[i].s;
  }
  vector<array<int, 4>> ft, st;
  rep(i, q) {
    int x, y, z;
    cin >> x >> y >> z;
    if (x + y >= z) {
      ft.push_back({x, y, z, i});
    } else {
      st.push_back({x, y, z, i});
    }
  }
  sort(all(a));
  sort(all(ft));
  fenwick<int> fenw_1(int(1e9) + 1);
  int ptr = n - 1;
  vi ans(q);
  per(i, sz(ft)) {
    while (a[ptr].f >= ft[i][0]) {
      fenw_1.modify(a[ptr].s, 1);
      ptr--;
    }
    ans[ft[i][3]] = fenw_1.get(int(1e9)) - fenw_1.get(ft[i][1] - 1);
  }
  rep(i, q) {
    cout << ans[i] << '\n';
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...