Submission #380808

#	Time	Username	Problem	Language	Result	Execution time	Memory
380808		2qbingxuan	Examination (JOI19_examination)	C++14	100 / 100	307 ms	14236 KiB

examination

#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) qqbx(#a, a)
#define pary(a...) danb(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\033[1;32m[ " << s << " ] = [ ";
    for (auto it = L; it != R; ++it)
        std::cerr << *it << ' ';
    std::cerr << "]\033[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define pb emplace_back
#define sort_uni(v) sort(all(v)),v.erase(unique(all(v)), v.end())
#define get_pos(u,v) int(lower_bound(all(u), v) - u.begin())

using namespace std;
using ll = int64_t;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using max_heap = priority_queue<T, vector<T>, less<T>>;
const int maxn = 300025, inf = 1e9, MOD = 1000000007;
const ll INF = 1e18;

namespace cdq {
    struct Event {
        int t;
        int x, y, z;
        int id;
    } E[maxn];
    int cnt;
    int ans[maxn];
    struct Fenwick {
        int sum[maxn];
        void add(int p, int d) {
            for (; p < maxn; p += p & -p) sum[p] += d;
        }
        int query(int p) {
            int r = 0;
            for (; p > 0; p -= p & -p) r += sum[p];
            return r;
        }
    } fwt;
    void addEvent(int t, int x, int y, int z, int id) {
        E[cnt++] = { t, x, y, z, id };
    }
    bool cmpy(Event a, Event b) {
        return a.y != b.y ? a.y < b.y :
               a.z != b.z ? a.z < b.z :
               a.t < b.t;
    }
    void solve(int l, int r) {
        if (l+1 >= r) return;
        int m = l+(r-l)/2;
        solve(l, m);
        solve(m, r);
        int i = l, j = m;
        while (i < m || j < r) {
            if (j == r || (i < m && cmpy(E[i], E[j]))) {
                auto e = E[i++];
                if (e.t == 0) {
                    fwt.add(e.z, 1);
                }
            } else {
                auto e = E[j++];
                if (e.t == 1) {
                    ans[e.id] += fwt.query(e.z);
                }
            }
        }
        for (int i = l; i < m; i++) if (E[i].t == 0) fwt.add(E[i].z, -1);
        inplace_merge(E+l, E+m, E+r, cmpy);
    }
    void solve() {
        vector<int> u;
        for (int i = 0; i < cnt; i++) u.emplace_back(E[i].z);
        sort_uni(u);
        sort(E, E+cnt, [](Event a, Event b){
            return a.x != b.x ? a.x < b.x : 
                   a.y != b.y ? a.y < b.y :
                   a.z != b.z ? a.z < b.z :
                   a.t < b.t;
        });
        for (int i = 0; i < cnt; i++)
            E[i].z = get_pos(u, E[i].z) + 1;
        solve(0, cnt);
    }
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        x = -x, y = -y;
        cdq::addEvent(0, x, y, x+y, -1);
    }
    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x = -x, y = -y, z = -z;
        cdq::addEvent(1, x, y, z, i);
    }
    safe;
    cdq::solve();
    for (int i = 0; i < q; i++)
        cout << cdq::ans[i] << '\n';
}

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