| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 522449 |
2022-02-05T04:10:51 Z |
KoD |
Sunčanje (COCI18_suncanje) |
C++17 |
|
2477 ms |
117448 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();
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
5780 KB |
Output is correct |
| 2 |
Correct |
97 ms |
8152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
14384 KB |
Output is correct |
| 2 |
Correct |
982 ms |
52536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
25716 KB |
Output is correct |
| 2 |
Correct |
1277 ms |
64636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
578 ms |
36008 KB |
Output is correct |
| 2 |
Correct |
1029 ms |
54308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1077 ms |
56784 KB |
Output is correct |
| 2 |
Correct |
1447 ms |
69300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1104 ms |
58972 KB |
Output is correct |
| 2 |
Correct |
1268 ms |
64764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1114 ms |
58712 KB |
Output is correct |
| 2 |
Correct |
1480 ms |
75384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1768 ms |
86476 KB |
Output is correct |
| 2 |
Correct |
1135 ms |
60976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1818 ms |
93144 KB |
Output is correct |
| 2 |
Correct |
1793 ms |
94480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2339 ms |
113988 KB |
Output is correct |
| 2 |
Correct |
2477 ms |
117448 KB |
Output is correct |
