test/aoj/2426.test.cpp

• View this file on GitHub
• Last update: 2025-07-07 14:21:50+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426

Depends on

• Merge Sort Tree (data_structure/merge_sort_tree.hpp)

Required by

• test/utility/next_combination.test.cpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426"

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

#include "../../data_structure/merge_sort_tree.hpp"

int main() {
    int N, M;
    cin >> N >> M;
    vector<pair<long long, long long>> pos(N);
    for (int i = 0; i < N; i++) {
        long long x, y;
        cin >> x >> y;
        pos[i] = make_pair(x, y);
    }

    sort(pos.begin(), pos.end());

    vector<long long> xv(N), yv(N);
    for (int i = 0; i < N; i++) {
        auto [x, y] = pos[i];

        xv[i] = x;
        yv[i] = y;
    }

    MergeSortTree<long long> mst(yv, LLONG_MAX);
    for (; M--;) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        int l = lower_bound(xv.begin(), xv.end(), x1) - xv.begin();
        int r = upper_bound(xv.begin(), xv.end(), x2) - xv.begin();

        int ans = mst.count(l, r, y2) - mst.count(l, r, y1 - 1);
        cout << ans << '\n';
    }

    return 0;
}

#line 1 "test/aoj/2426.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426"

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

#line 2 "data_structure/merge_sort_tree.hpp"

/**
 * @brief Merge Sort Tree
 */
template <class T>
class MergeSortTree {
  private:
    int n;
    vector<vector<T>> v, s;

    void update(int i) {
        v[i].clear();
        v[i].reserve(v[i << 1].size() + v[(i << 1) | 1].size());

        merge(v[i << 1].begin(), v[i << 1].end(), v[(i << 1) | 1].begin(),
              v[(i << 1) | 1].end(), back_inserter(v[i]));

        s[i] = vector<T>(v[i].size() + 1);
        for (int j = 0; j < int(v[i].size()); j++) {
            s[i][j + 1] = s[i][j] + v[i][j];
        }
    }

  public:
    MergeSortTree(const vector<T>& _v, const T& inf) {
        n = 1;
        while (n < int(_v.size())) {
            n <<= 1;
        }

        v = vector<vector<T>>(n * 2);
        s = vector<vector<T>>(n * 2);

        for (int i = 0; i < n; i++) {
            if (i < int(_v.size())) {
                v[n + i] = vector<T>({_v[i]});
                s[n + i] = vector<T>({T(0), _v[i]});
            } else {
                v[n + i] = vector<T>({inf});
                s[n + i] = vector<T>({T(0), inf});
            }
        }

        for (int i = n - 1; i >= 1; i--) {
            update(i);
        }
    }

    /**
     * @brief [l, r)に含まれるa以下の数の総和
     */
    T sum(int l, int r, const T& a) const {
        l += n;
        r += n;
        T res = 0;
        while (l < r) {
            if (l & 1) {
                int t = upper_bound(v[l].begin(), v[l].end(), a) - v[l].begin();
                res += s[l][t];
                l++;
            }
            if (r & 1) {
                r--;
                int t = upper_bound(v[r].begin(), v[r].end(), a) - v[r].begin();
                res += s[r][t];
            }
            l >>= 1;
            r >>= 1;
        }

        return res;
    }

    /**
     * @brief [l, r)に含まれるa以下の数の個数
     */
    int count(int l, int r, const T& a) const {
        l += n;
        r += n;

        int res = 0;
        while (l < r) {
            if (l & 1) {
                int t = upper_bound(v[l].begin(), v[l].end(), a) - v[l].begin();
                res += t;
                l++;
            }
            if (r & 1) {
                r--;
                int t = upper_bound(v[r].begin(), v[r].end(), a) - v[r].begin();
                res += t;
            }
            l >>= 1;
            r >>= 1;
        }

        return res;
    }
};
#line 7 "test/aoj/2426.test.cpp"

int main() {
    int N, M;
    cin >> N >> M;
    vector<pair<long long, long long>> pos(N);
    for (int i = 0; i < N; i++) {
        long long x, y;
        cin >> x >> y;
        pos[i] = make_pair(x, y);
    }

    sort(pos.begin(), pos.end());

    vector<long long> xv(N), yv(N);
    for (int i = 0; i < N; i++) {
        auto [x, y] = pos[i];

        xv[i] = x;
        yv[i] = y;
    }

    MergeSortTree<long long> mst(yv, LLONG_MAX);
    for (; M--;) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        int l = lower_bound(xv.begin(), xv.end(), x1) - xv.begin();
        int r = upper_bound(xv.begin(), xv.end(), x2) - xv.begin();

        int ans = mst.count(l, r, y2) - mst.count(l, r, y1 - 1);
        cout << ans << '\n';
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	testcase_00	AC	5 ms	4 MB
g++	testcase_01	AC	5 ms	3 MB
g++	testcase_02	AC	5 ms	4 MB
g++	testcase_03	AC	5 ms	3 MB
g++	testcase_04	AC	4 ms	3 MB
g++	testcase_05	AC	1220 ms	7 MB
g++	testcase_06	AC	1251 ms	6 MB
g++	testcase_07	AC	1391 ms	7 MB
g++	testcase_08	AC	1205 ms	7 MB
g++	testcase_09	AC	10 ms	4 MB
g++	testcase_10	AC	7 ms	4 MB
g++	testcase_11	AC	6 ms	4 MB
g++	testcase_12	AC	11 ms	4 MB
g++	testcase_13	AC	6 ms	4 MB
g++	testcase_14	AC	900 ms	4 MB
g++	testcase_15	AC	549 ms	4 MB
g++	testcase_16	AC	530 ms	7 MB
g++	testcase_17	AC	1762 ms	5 MB
g++	testcase_18	AC	984 ms	4 MB
g++	testcase_19	AC	1654 ms	7 MB
g++	testcase_20	AC	1654 ms	7 MB
g++	testcase_21	AC	1722 ms	7 MB
g++	testcase_22	AC	1736 ms	7 MB
g++	testcase_23	AC	1710 ms	7 MB

Back to top page