Submission #522448

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
522448	2022-02-05T04:10:36 Z	KoD	Sunčanje (COCI18_suncanje)	C++17	130 / 130	2575 ms	120424 KB

suncanje

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::tuple;
using std::pair;

int dedup(vector<int>& v) {
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    return v.size();
}

int lowb(const vector<int>& v, const int x) {
    return std::lower_bound(v.begin(), v.end(), x) - v.begin();
}

int upb(const vector<int>& v, const int x) {
    return std::upper_bound(v.begin(), v.end(), x) - v.begin();
}

struct Fenwick {
    int size;
    vector<int> data;
    Fenwick() = default;
    Fenwick(const int n) : size(n), data(n + 1) {}
    void add(int i) {
        i += 1;
        while (i <= size) {
            data[i] += 1;
            i += i & -i;
        }
    }
    int pref(int i) const {
        int ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= i & -i;
        }
        return ret;
    }
    int fold(const int l, const int r) const {
        return pref(r) - pref(l);
    }
};

struct Sum2D {
    int X, Y;
    vector<vector<int>> pts;
    vector<Fenwick> fen;
    Sum2D(const int x, const int y) : X(x), Y(y), pts(X + 1), fen(X + 1) {}
    void set(int x, int y) {
        x += 1;
        while (x <= X) {
            pts[x].push_back(y);
            x += x & -x;
        }
    }
    void build() {
        for (int x = 1; x <= X; ++x) {
            dedup(pts[x]);
            fen[x] = Fenwick(pts[x].size());
        }
    }
    void add(int x, int y) {
        x += 1;
        while (x <= X) {
            fen[x].add(lowb(pts[x], y));
            x += x & -x;
        }
    }
    int pref(int x, const int u, const int d) const {
        int ret = 0;
        while (x > 0) {
            ret += fen[x].fold(lowb(pts[x], u), lowb(pts[x], d));
            x -= x & -x;
        }
        return ret;
    }
    int fold(const int l, const int r, const int u, const int d) const {
        return pref(r, u, d) - pref(l, u, d);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<int> A(N), B(N), C(N), D(N);
    for (int i = 0; i < N; ++i) {
        int x, y, a, b;
        std::cin >> x >> y >> a >> b;
        A[i] = x, B[i] = y, C[i] = x + a, D[i] = y + b;
    }
    vector<int> cX, cY;
    cX.reserve(2 * N);
    std::copy(A.begin(), A.end(), std::back_inserter(cX));
    std::copy(C.begin(), C.end(), std::back_inserter(cX));
    std::copy(B.begin(), B.end(), std::back_inserter(cY));
    std::copy(D.begin(), D.end(), std::back_inserter(cY));
    const int nX = dedup(cX);
    const int nY = dedup(cY);
    for (auto& x : A) {
        x = lowb(cX, x);
    }
    for (auto& x : C) {
        x = lowb(cX, x);
    }
    for (auto& y : B) {
        y = lowb(cY, y);
    }
    for (auto& y : D) {
        y = lowb(cY, y);
    }
    Sum2D ld(nX, nY), rd(nX, nY), lu(nX, nY), ru(nX, nY);
    for (int i = 0; i < N; ++i) {
        ld.set(C[i], D[i]);
        rd.set(A[i], D[i]);
        lu.set(C[i], B[i]);
        ru.set(A[i], B[i]);
    }
    ld.build();
    rd.build();
    lu.build();
    ru.build();
    Fenwick l(nX), r(nX), d(nY), u(nY);
    vector<int> ans(N);
    for (int i = N - 1; i >= 0; --i) {
        ans[i] = N - i - 1;
        ans[i] -= l.fold(0, A[i] + 1);
        ans[i] -= r.fold(C[i], nX);
        ans[i] -= d.fold(0, B[i] + 1);
        ans[i] -= u.fold(D[i], nY);
        ans[i] += ld.fold(0, A[i] + 1, 0, B[i] + 1);
        ans[i] += rd.fold(C[i], nX, 0, B[i] + 1);
        ans[i] += lu.fold(0, A[i] + 1, D[i], nY);
        ans[i] += ru.fold(C[i], nX, D[i], nY);
        l.add(C[i]);
        r.add(A[i]);
        d.add(D[i]);
        u.add(B[i]);
        ld.add(C[i], D[i]);
        rd.add(A[i], D[i]);
        lu.add(C[i], B[i]);
        ru.add(A[i], B[i]);
    }
    for (const int c : ans) {
        std::cout << (c ? "NE" : "DA") << '\n';
    }
    return 0;
}

Subtask #1
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	5880 KB	Output is correct
2	Correct	72 ms	8096 KB	Output is correct

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	14252 KB	Output is correct
2	Correct	870 ms	53792 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	329 ms	25720 KB	Output is correct
2	Correct	1095 ms	66320 KB	Output is correct

Subtask #4
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	577 ms	36016 KB	Output is correct
2	Correct	861 ms	55620 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	999 ms	56792 KB	Output is correct
2	Correct	1281 ms	70976 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1038 ms	58980 KB	Output is correct
2	Correct	1178 ms	66300 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1047 ms	58660 KB	Output is correct
2	Correct	1453 ms	75376 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1895 ms	86612 KB	Output is correct
2	Correct	1155 ms	61100 KB	Output is correct

Subtask #9
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2135 ms	93276 KB	Output is correct
2	Correct	2129 ms	96880 KB	Output is correct

Subtask #10
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2575 ms	114212 KB	Output is correct
2	Correct	2559 ms	120424 KB	Output is correct

Submission #522448

Compilation message