Submission #1184819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184819		mannshah1211	Examination (JOI19_examination)	C++17	100 / 100	1500 ms	162016 KiB

examination

#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), fenw_2(int(2e9) + 1), fenw_3(int(2e9) + 1);
  int ptr = n - 1;
  vi ans(q);
  per(i, sz(ft)) {
    while (ptr >= 0 && 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);
  }
  sort(all(a), [&](pair<int, int> x, pair<int, int> y) {
    return (x.s < y.s);
  });
  sort(all(st), [&](array<int, 4> aa, array<int, 4> ab) {
    return (aa[1] < ab[1]);
  });
  ptr = n - 1;
  per(i, sz(st)) {
    while (ptr >= 0 && a[ptr].s >= st[i][1]) {
      fenw_2.modify(a[ptr].f + a[ptr].s, 1);
      ptr--;
    }
    ans[st[i][3]] = fenw_2.get(int(2e9)) - fenw_2.get(st[i][2] - 1);
  }
  ptr = 0;
  sort(all(st));
  sort(all(a));
  rep(i, sz(st)) {
    while (ptr < n && a[ptr].f < st[i][0]) {
      fenw_3.modify(a[ptr].f + a[ptr].s, 1);
      ptr++;
    }
    ans[st[i][3]] -= (fenw_3.get(int(2e9)) - fenw_3.get(st[i][2] - 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;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57