Submission #1341956

#TimeUsernameProblemLanguageResultExecution timeMemory
1341956lto5Examination (JOI19_examination)C++20
100 / 100
324 ms31228 KiB
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct FT {
  vector<ll> s;
  FT(int n) : s(n + 1) {}
  void update(int pos, ll dif) {
    pos++;
    for (; pos > 0; pos -= pos & -pos) s[pos] += dif;
  }
  ll query(int pos) {
    pos++;
    ll res = 0;
    for (; pos < sz(s); pos += pos & -pos) res += s[pos];
    return res;
  }
};

struct FT2 {
  vector<vi> ys;
  vector<FT> ft;
  FT2(int limx) : ys(limx) {}
  void fakeUpdate(int x, int y) {
    for (; x > 0; x -= x & -x) ys[x].push_back(y);
  }
  void init() {
    for (vi& v : ys) {
      sort(all(v));
      v.erase(unique(all(v)), v.end());
      ft.emplace_back(sz(v));
    }
  }
  int ind(int x, int y) {
    return (int)(lower_bound(all(ys[x]), y) - ys[x].begin());
  }
  void update(int x, int y, ll dif) {
    for (; x > 0; x -= x & -x) ft[x].update(ind(x, y), dif);
  }
  ll query(int x, int y) {
    ll sum = 0;
    for (; x < sz(ys); x += x & -x) sum += ft[x].query(ind(x, y));
    return sum;
  }
};

template <typename Iterator>
void compressor(Iterator begin, Iterator end) {
  using ValueType = typename std::iterator_traits<Iterator>::value_type;
  std::vector<std::pair<ValueType, Iterator>> arr;
  for (auto it = begin; it != end; ++it) {
    arr.emplace_back(*it, it);
  }
  std::sort(arr.begin(), arr.end(),
            [](const auto& a, const auto& b) { return a.first < b.first; });
  int cnt = 1;
  for (int i = 0; i < (int)arr.size(); ++i) {
    if (i > 0 && arr[i].first != arr[i - 1].first) {
      ++cnt;
    }
    *arr[i].second = cnt;
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL
#define task "a"
#else
#define task "ANHDEP"
#endif
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  int n, q;
  cin >> n >> q;
  vector<pair<int, int>> a(n);
  for (auto& [x, y] : a) cin >> x >> y;
  sort(a.rbegin(), a.rend());
  vector<array<int, 4>> qr(q);
  vector<int> ans(q);
  for (int i = 0; i < q; i++) {
    cin >> qr[i][0] >> qr[i][1] >> qr[i][2];
    qr[i][3] = i;
  }
  vector<int> ys(n + q), xys(n + q);
  for (int i = 0; i < n; i++)
    ys[i] = a[i].second, xys[i] = a[i].second + a[i].first;
  for (int i = 0; i < q; i++) ys[i + n] = qr[i][1], xys[i + n] = qr[i][2];
  sort(qr.rbegin(), qr.rend());
  compressor(ys.begin(), ys.end());
  compressor(xys.begin(), xys.end());
  FT2 ft2(n + q + 5);
  for (int i = 0; i < n; i++) {
    ft2.fakeUpdate(ys[i], xys[i]);
  }
  ft2.init();
  int j = 0;
  for (auto [x, y, z, i] : qr) {
    while (j < n && a[j].first >= x) {
      ft2.update(ys[j], xys[j], 1);
      // cerr << "add " << ys[j] << " " << xys[j] << endl;
      ++j;
    }
    ans[i] = ft2.query(ys[i + n], xys[i + n]);
  }
  for (auto it : ans) cout << it << '\n';
  return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:81:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...