Submission #1215990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215990		akamizane	Examination (JOI19_examination)	C++20	100 / 100	372 ms	49968 KiB

examination

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

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 42
#endif

#define int long long

template <typename T> class OfflineFenwick2D {
  private:
    const int n;
    vector<vector<int>> vals;
    vector<vector<T>> arr;

    int ind(const vector<int> &v, int x) {
        return upper_bound(begin(v), end(v), x) - begin(v) - 1;
    }

  public:
    OfflineFenwick2D(int _n, vector<array<int, 2>> &todo)
        : n(_n), vals(n + 1), arr(n + 1) {
        sort(begin(todo), end(todo), 
            [](const array<int, 2> &a, const array<int, 2> &b) -> bool {
            return a[1] < b[1];
        });
        for (int i = 1; i <= n; i++) { vals[i].push_back(0); }
        for (auto [r, c] : todo) {
            r++, c++;
            for (; r <= n; r += r & -r) {
                if (vals[r].back() != c) { vals[r].push_back(c); }
            }
        }
        for (int i = 1; i <= n; i++) {
            arr[i].resize(vals[i].size());
        }
    }

    /** adds val to the point (r, c) */
    void add(int r, int c, T val) {
        r++, c++;
        for (; r <= n; r += r & -r) {
            int i = ind(vals[r], c);
            for (; i < arr[r].size(); i += i & -i) {
                arr[r][i] += val;
            }
        }
    }

    /** @return rectangle sum for corners (0, 0), (r, c) */
    T rect_sum(int r, int c) {
        r++, c++;
        T sum = 0;
        for (; r > 0; r -= r & -r) {
            int i = ind(vals[r], c);
            for (; i > 0; i -= i & -i) {
                sum += arr[r][i];
            }
        }
        return sum;
    }

    /** @return rectangle sum with corners (r1, c1) and (r2, c2) */
    T rect_sum(int r1, int c1, int r2, int c2) {
        return rect_sum(r2, c2) - rect_sum(r2, c1 - 1) - 
               rect_sum(r1 - 1, c2) + rect_sum(r1 - 1, c1 - 1);
    }
};

void solve(){
   int n, q;
   cin >> n >> q;
   using T = array<int, 5>;
   vector<T> op;
   vector<int> y_val;
   for (int i = 0; i < n; i++){
      int s, t;
      cin >> s >> t;
      op.push_back({0, s, t, s + t, -1});
      y_val.push_back(t);
   }
   for (int i = 0; i < q; i++){
      int x, y, z;
      cin >> x >> y >> z;
      op.push_back({1, x, y, z, i});
      y_val.push_back(y);
   }
   sort(op.begin(), op.end(), [&] (T x, T y){
      return (x[1] == y[1]) ? x[0] < y[0] : x[1] > y[1];
   });
   sort(y_val.begin(), y_val.end());
   y_val.erase(unique(y_val.begin(), y_val.end()), y_val.end());
   debug(op);
   vector<array<int, 2>> que;
   for (auto& [t, x, y, sum, idx] : op){
      y = lower_bound(y_val.begin(), y_val.end(), y) - y_val.begin();
      if (t == 0){
         que.push_back({y, sum});
      }
   }
   vector<int> ans(q);
   OfflineFenwick2D<int> bit(y_val.size(), que);
   for (auto [t, x, y, sum, idx] : op){
      if (t == 0){
         bit.add(y, sum, 1);
      }
      else {
         ans[idx] = bit.rect_sum(y, sum, y_val.size() - 1, 2e9);
      }
   }
   for (auto x : ans) cout << x << "\n";
}

int32_t main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   int tt = 1;
   // cin >> tt;
   while(tt--) {
      solve();
   }
   return 0;
}

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