#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("no-stack-protector")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define PB push_back
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define MP make_pair
#define ft first
#define sd second
#define sz(x) ((int)x.size())
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
const int N = 100100;
const int PW = 22;
const int oo = 2e9;
vector<int> xs, ys;
bool mrk[N];
int x1[N], Y1[N], x2[N], y2[N], n, IND;
ordered_set<pii> up, down, Left, Right;
struct BIT{
vector<int> elements;
vector<int> fen;
int kol;
BIT(): elements(0), fen(0), kol(0) {}
void insert(int x){
elements.PB(x);
}
void build(){
sort(all(elements));
elements.resize(unique(all(elements)) - elements.begin());
fen.resize(sz(elements));
}
void update(int x){
x = lower_bound(all(elements), x) - elements.begin();
kol++;
for (int v = x; v < sz(fen); v = (v | (v + 1)))
fen[v]++;
}
int sum(int x){
x = upper_bound(all(elements), x) - elements.begin() - 1;
int res = 0;
for (int v = x; v >= 0; v = (v & (v + 1)) - 1)
res += fen[v];
return res;
}
};
BIT st[4][N];
int get_up_left(int x, int y){
int res = 0;
for (int v = x; v >= 0; v = (v & (v + 1)) - 1)
res += st[0][v].kol - st[0][v].sum(y - 1);
return res;
}
int get_down_left(int x, int y){
int res = 0;
for (int v = x; v >= 0; v = (v & (v + 1)) - 1)
res += st[2][v].sum(y);
return res;
}
int get_up_right(int x, int y){
int res = 0;
for (int v = x; v >= 0; v = (v & (v + 1)) - 1)
res += st[1][v].kol - st[1][v].sum(y - 1);
return res;
}
int get_down_right(int x, int y){
int res = 0;
for (int v = x; v >= 0; v = (v & (v + 1)) - 1)
res += st[3][v].sum(y);
return res;
}
void update_fi(int tp, int x, int y){
for (int v = x; v < sz(xs); v = (v | (v + 1)))
st[tp][v].update(y);
}
void update_fis(int tp, int x, int y){
for (int v = x; v < sz(ys); v = (v | (v + 1)))
st[tp][v].update(y);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n;
for (int i = 0; i < n; i++){
int X, Y; cin >> x1[i] >> Y1[i] >> X >> Y;
x2[i] = x1[i] + X;
y2[i] = Y1[i] + Y;
xs.PB(x1[i]);
ys.PB(x2[i]);
}
sort(all(xs));
sort(all(ys));
xs.resize(unique(all(xs)) - xs.begin());
ys.resize(unique(all(ys)) - ys.begin());
up.clear();
down.clear();
Left.clear();
Right.clear();
// build correct BIT-s
for (int i = 0; i < n; i++){
int loc = lower_bound(all(ys), x2[i]) - ys.begin();
for (int v = loc; v < sz(ys); v = (v | (v + 1)))
st[0][v].insert(Y1[i]);
loc = lower_bound(all(xs), x1[i]) - xs.begin();
for (int v = sz(xs) - 1 - loc; v < sz(xs); v = (v | (v + 1)))
st[1][v].insert(Y1[i]);
loc = lower_bound(all(ys), x2[i]) - ys.begin();
for (int v = loc; v < sz(ys); v = (v | (v + 1)))
st[2][v].insert(y2[i]);
loc = lower_bound(all(xs), x1[i]) - xs.begin();
for (int v = sz(xs) - 1 - loc; v < sz(xs); v = (v | (v + 1)))
st[3][v].insert(y2[i]);
}
for (int i = 0; i < sz(xs); i++){
st[1][i].build();
st[3][i].build();
}
for (int i = 0; i < sz(xs); i++){
st[0][i].build();
st[2][i].build();
}
for (int i = n - 1; i >= 0; i--){
if (i < n - 1){
int kol = 0;
kol += sz(up) - up.order_of_key(MP(y2[i] - 1, oo));
kol += Left.order_of_key(MP(x1[i], oo));
kol += down.order_of_key(MP(Y1[i], oo));
kol += sz(Right) - Right.order_of_key(MP(x2[i] - 1, oo));
int loc = upper_bound(all(ys), x1[i]) - ys.begin() - 1;
kol -= get_up_left(loc, y2[i]);
loc = upper_bound(all(ys), x1[i]) - ys.begin() - 1;
kol -= get_down_left(loc, Y1[i]);
loc = lower_bound(all(xs), x2[i]) - xs.begin();
kol -= get_up_right(sz(xs) - 1 - loc, y2[i]);
loc = lower_bound(all(xs), x2[i]) - xs.begin();
kol -= get_down_right(sz(xs) - 1 - loc, Y1[i]);
if (kol < n - i - 1)
mrk[i] = 1;
}
// add new elements
up.insert(MP(Y1[i], i));
down.insert(MP(y2[i], i));
Left.insert(MP(x2[i], i));
Right.insert(MP(x1[i], i));
IND = i;
int loc = lower_bound(all(ys), x2[i]) - ys.begin();
update_fis(2, loc, y2[i]);
loc = lower_bound(all(xs), x1[i]) - xs.begin();
update_fi(3, sz(xs) - 1 - loc, y2[i]);
loc = lower_bound(all(ys), x2[i]) - ys.begin();
update_fis(0, loc, Y1[i]);
loc = lower_bound(all(xs), x1[i]) - xs.begin();
update_fi(1, sz(xs) - 1 - loc, Y1[i]);
}
for (int i = 0; i < n; i++)
cout << (mrk[i] ? "NE\n" : "DA\n");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
25720 KB |
Output is correct |
| 2 |
Correct |
101 ms |
27000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
218 ms |
31096 KB |
Output is correct |
| 2 |
Correct |
1070 ms |
54772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
458 ms |
38008 KB |
Output is correct |
| 2 |
Correct |
1419 ms |
62304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
684 ms |
44536 KB |
Output is correct |
| 2 |
Correct |
1106 ms |
55924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1201 ms |
57716 KB |
Output is correct |
| 2 |
Correct |
1519 ms |
65648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1296 ms |
59520 KB |
Output is correct |
| 2 |
Correct |
1418 ms |
63124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1223 ms |
59052 KB |
Output is correct |
| 2 |
Correct |
1726 ms |
69112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2054 ms |
76952 KB |
Output is correct |
| 2 |
Correct |
1315 ms |
60296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2306 ms |
82128 KB |
Output is correct |
| 2 |
Correct |
2287 ms |
82896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2853 ms |
94572 KB |
Output is correct |
| 2 |
Correct |
2981 ms |
97680 KB |
Output is correct |
