oj.uz

답안 #380807

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380807 2021-03-23T03:47:30 Z 2qbingxuan Examination (JOI19_examination) C++14
2 / 100
 23 ms 5868 KB 
#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 = 100025, 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.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 9 ms 748 KB Output is correct
8 Correct 8 ms 748 KB Output is correct
9 Correct 8 ms 748 KB Output is correct
10 Correct 7 ms 748 KB Output is correct
11 Correct 7 ms 748 KB Output is correct
12 Correct 5 ms 620 KB Output is correct
13 Correct 7 ms 748 KB Output is correct
14 Correct 7 ms 748 KB Output is correct
15 Correct 7 ms 748 KB Output is correct
16 Correct 5 ms 748 KB Output is correct
17 Correct 7 ms 748 KB Output is correct
18 Correct 4 ms 620 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 5868 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 5868 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 9 ms 748 KB Output is correct
8 Correct 8 ms 748 KB Output is correct
9 Correct 8 ms 748 KB Output is correct
10 Correct 7 ms 748 KB Output is correct
11 Correct 7 ms 748 KB Output is correct
12 Correct 5 ms 620 KB Output is correct
13 Correct 7 ms 748 KB Output is correct
14 Correct 7 ms 748 KB Output is correct
15 Correct 7 ms 748 KB Output is correct
16 Correct 5 ms 748 KB Output is correct
17 Correct 7 ms 748 KB Output is correct
18 Correct 4 ms 620 KB Output is correct
19 Runtime error 23 ms 5868 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -