/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author
*/
#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
struct Fenwick {
vector<int> f;
Fenwick() {}
Fenwick(int n) {
f.resize(n + 2);
}
void update(int i, int v) {
++i;
while(i < f.size()) f[i] += v, i += i & -i;
}
int query(int i) {
++i;
int ret = 0;
while(i > 0) ret += f[i], i -= i & -i;
return ret;
}
};
struct MST {
int n;
vector<vector<int> > ls;
vector<Fenwick> t;
MST() {}
MST(int n): n(n) {
ls.resize(2*n);
t.resize(2*n);
}
void clear() {
for(int i = 1; i < 2*n; i++) fill(t[i].f.begin(), t[i].f.end(), 0);
}
void add_value(int x, int y) {
ls[x + n].push_back(y);
}
void build() {
for(int i = n; i < 2*n; i++) {
sort(ls[i].begin(), ls[i].end());
ls[i].resize(unique(ls[i].begin(), ls[i].end()) - ls[i].begin());
t[i] = Fenwick(ls[i].size());
}
for(int i = n-1; i >= 1; i--) { // not in order?
// cout << i << endl;
merge(ls[i << 1].begin(), ls[i << 1].end(), ls[i << 1 | 1].begin(), ls[i << 1 | 1].end(), back_inserter(ls[i]));
ls[i].resize(unique(ls[i].begin(), ls[i].end()) - ls[i].begin());
// for(int x: ls[i]) cout << x << ' ';
// cout << endl;
t[i] = Fenwick(ls[i].size());
}
}
void update(int x, int y) {
for(x += n; x >= 1; x >>= 1) {
auto it = lower_bound(ls[x].begin(), ls[x].end(), y);
t[x].update(it - ls[x].begin(), 1);
}
}
int query(int x1, int y1, int x2, int y2) {
int ret = 0;
for(x1 += n, x2 += n+1; x1 < x2; x1 >>= 1, x2 >>= 1) {
if(x1 & 1) {
auto ity1 = lower_bound(ls[x1].begin(), ls[x1].end(), y1);
auto ity2 = upper_bound(ls[x1].begin(), ls[x1].end(), y2);
if(ity1 != ls[x1].end()) {
ret += t[x1].query(ity2 - ls[x1].begin() - 1) - t[x1].query(ity1 - ls[x1].begin() - 1);
}
++x1;
}
if(x2 & 1) {
--x2;
auto ity1 = lower_bound(ls[x2].begin(), ls[x2].end(), y1);
auto ity2 = upper_bound(ls[x2].begin(), ls[x2].end(), y2);
if(ity1 != ls[x2].end()) {
ret += t[x2].query(ity2 - ls[x2].begin() - 1) - t[x2].query(ity1 - ls[x2].begin() - 1);
}
}
}
return ret;
}
};
class Suncanje {
int n;
vector<tuple<int,int,int,int> > a;
vector<int> res;
vector<string> ans;
MST mst1, mst2;
Fenwick fen[4];
vector<int> xs, ys;
void compress() {
for(int i = 0, x1, y1, x2, y2; i < n; i++) {
tie(x1, y1, x2, y2) = a[i];
xs.push_back(x1);
xs.push_back(x2);
ys.push_back(y1);
ys.push_back(y2);
}
sort(xs.begin(), xs.end());
xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
sort(ys.begin(), ys.end());
ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
for(auto &tt: a) {
int x1, y1, x2, y2;
tie(x1, y1, x2, y2) = tt;
auto it = lower_bound(xs.begin(), xs.end(), x1);
get<0>(tt) = it - xs.begin();
it = lower_bound(xs.begin(), xs.end(), x2);
get<2>(tt) = it - xs.begin();
it = lower_bound(ys.begin(), ys.end(), y1);
get<1>(tt) = it - ys.begin();
it = lower_bound(ys.begin(), ys.end(), y2);
get<3>(tt) = it - ys.begin();
}
}
public:
void solve(istream &cin, ostream &cout) {
cin >> n;
for(int i = 0, x1, y1, A, B; i < n; i++) {
cin >> x1 >> y1 >> A >> B;
a.emplace_back(x1, y1, x1 + A, y1 + B);
}
res.resize(n);
compress();
reverse(a.begin(), a.end());
int sz = max(xs.size(), ys.size());
for(int i = 0; i < 4; i++) fen[i] = Fenwick(sz);
mst1 = MST(xs.size());
mst2 = MST(xs.size());
for(auto tt: a) {
int x1, y1, x2, y2;
tie(x1, y1, x2, y2) = tt;
mst1.add_value(x1, y1);
mst1.add_value(x1, y2);
mst2.add_value(x2, y1);
mst2.add_value(x2, y2);
}
mst1.build();
mst2.build();
int x1, y1, x2, y2;
for(int i = 0; i < n; i++) {
tie(x1, y1, x2, y2) = a[i];
res[i] -= mst1.query(x2, y2, xs.size() - 1, ys.size() - 1);
mst1.update(x1, y1);
}
mst1.clear();
for(int i = 0; i < n; i++) {
tie(x1, y1, x2, y2) = a[i];
res[i] -= mst1.query(x2, 0, xs.size() - 1, y1);
mst1.update(x1, y2);
}
for(int i = 0; i < n; i++) {
tie(x1, y1, x2, y2) = a[i];
res[i] -= mst2.query(0, y2, x1, ys.size() - 1);
mst2.update(x2, y1);
}
mst2.clear();
for(int i = 0; i < n; i++) {
tie(x1, y1, x2, y2) = a[i];
res[i] -= mst2.query(0, 0, x1, y1);
mst2.update(x2, y2);
}
for(int i = 0; i < n; i++) {
tie(x1, y1, x2, y2) = a[i];
res[i] += fen[2].query(x1) + i - fen[0].query(x2 - 1);
res[i] += fen[3].query(y1) + i - fen[1].query(y2 - 1);
fen[0].update(x1, 1);
fen[1].update(y1, 1);
fen[2].update(x2, 1);
fen[3].update(y2, 1);
}
reverse(res.begin(), res.end());
for(int i = 0; i < n; i++) cout << (res[i] == n - i - 1 ? "DA\n" : "NE\n");
}
};
class Solver {
public:
void solve(std::istream& in, std::ostream& out) {
Suncanje *obj = new Suncanje();
obj->solve(in, out);
delete obj;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solver solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
Compilation message
suncanje.cpp: In member function 'void Fenwick::update(int, int)':
suncanje.cpp:23:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < f.size()) f[i] += v, i += i & -i;
~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
69 ms |
6904 KB |
Output is correct |
| 2 |
Correct |
103 ms |
9592 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
220 ms |
17024 KB |
Output is correct |
| 2 |
Correct |
1211 ms |
63736 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
494 ms |
31092 KB |
Output is correct |
| 2 |
Correct |
1767 ms |
78688 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
819 ms |
43864 KB |
Output is correct |
| 2 |
Correct |
1425 ms |
65776 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1569 ms |
69576 KB |
Output is correct |
| 2 |
Correct |
1632 ms |
84336 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1297 ms |
71708 KB |
Output is correct |
| 2 |
Correct |
1487 ms |
78804 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1626 ms |
71112 KB |
Output is correct |
| 2 |
Correct |
2256 ms |
92916 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2857 ms |
104768 KB |
Output is correct |
| 2 |
Correct |
1729 ms |
74352 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3008 ms |
113408 KB |
Output is correct |
| 2 |
Correct |
2591 ms |
115036 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3492 ms |
140408 KB |
Output is correct |
| 2 |
Correct |
3203 ms |
143024 KB |
Output is correct |
