oj.uz

Submission #522442

# Submission time Handle Problem Language Result Execution time Memory
522442 2022-02-05T03:53:21 Z KoD Sunčanje (COCI18_suncanje) C++17
13 / 130
 2455 ms 117172 KB 
#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 char c : ans) {
        std::cout << (c ? "NE" : "DA") << '\n';
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5944 KB Output is correct
2 Correct 87 ms 8332 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 14688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 335 ms 26452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 574 ms 37052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 927 ms 58324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 965 ms 60608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1101 ms 60236 KB Output is correct
2 Incorrect 1425 ms 77540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1704 ms 88872 KB Output is correct
2 Incorrect 1082 ms 62692 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1871 ms 95588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2455 ms 117172 KB Output isn't correct
2 Halted 0 ms 0 KB -