#include <bits/stdc++.h>
#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,unsigned short>
#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, st[4][2 * N];
int get_up_left(int v, int tl, int tr, int x, int y){
if (ys[tl] > x || !sz(st[0][v])) return 0;
if (ys[tr] <= x) return sz(st[0][v]) - st[0][v].order_of_key(MP(y - 1, oo));
int md = (tl + tr) >> 1;
return get_up_left(v + v, tl, md, x, y) + get_up_left(v + v + 1, md + 1, tr, x, y);
}
int get_down_left(int v, int tl, int tr, int x, int y){
if (ys[tl] > x || !sz(st[2][v])) return 0;
if (ys[tr] <= x) return st[2][v].order_of_key(MP(y, oo));
int md = (tl + tr) >> 1;
return get_down_left(v + v, tl, md, x, y) + get_down_left(v + v + 1, md + 1, tr, x, y);
}
int get_up_right(int v, int tl, int tr, int x, int y){
if (xs[tr] < x || !sz(st[1][v])) return 0;
if (xs[tl] >= x) return sz(st[1][v]) - st[1][v].order_of_key(MP(y - 1, oo));
int md = (tl + tr) >> 1;
return get_up_right(v + v, tl, md, x, y) + get_up_right(v + v + 1, md + 1, tr, x, y);
}
int get_down_right(int v, int tl, int tr, int x, int y){
if (xs[tr] < x || !sz(st[3][v])) return 0;
if (xs[tl] >= x) return st[3][v].order_of_key(MP(y, oo));
int md = (tl + tr) >> 1;
return get_down_right(v + v, tl, md, x, y) + get_down_right(v + v + 1, md + 1, tr, x, y);
}
void update_fi(int tp, int v, int l, int r, int x, int y){
st[tp][v].insert(MP(y, IND));
if (l == r) return;
int md = (l + r) >> 1;
if (xs[md] >= x)
update_fi(tp, v + v, l, md, x, y);
else update_fi(tp, v + v + 1, md + 1, r, x, y);
}
void update_se(int tp, int v, int l, int r, int x, int y){
st[tp][v].insert(MP(y, IND));
if (l == r) return;
int md = (l + r) >> 1;
if (xs[md] >= x)
update_se(tp, v + v, l, md, x, y);
else update_se(tp, v + v + 1, md + 1, r, x, y);
}
// ses
void update_fis(int tp, int v, int l, int r, int x, int y){
st[tp][v].insert(MP(y, IND));
if (l == r) return;
int md = (l + r) >> 1;
if (ys[md] >= x)
update_fis(tp, v + v, l, md, x, y);
else update_fis(tp, v + v + 1, md + 1, r, x, y);
}
void update_ses(int tp, int v, int l, int r, int x, int y){
st[tp][v].insert(MP(y, IND));
if (l == r) return;
int md = (l + r) >> 1;
if (ys[md] >= x)
update_ses(tp, v + v, l, md, x, y);
else update_ses(tp, v + v + 1, md + 1, r, x, 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();
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));
kol -= get_up_left(1, 0, sz(ys) - 1, x1[i], y2[i]);
kol -= get_down_left(1, 0, sz(ys) - 1, x1[i], Y1[i]);
kol -= get_up_right(1, 0, sz(xs) - 1, x2[i], y2[i]);
kol -= get_down_right(1, 0, sz(xs) - 1, x2[i], 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;
update_fis(2, 1, 0, sz(ys) - 1, x2[i], y2[i]);
update_fi(3, 1, 0, sz(xs) - 1, x1[i], y2[i]);
update_ses(0, 1, 0, sz(ys) - 1, x2[i], Y1[i]);
update_se(1, 1, 0, sz(xs) - 1, x1[i], 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 |
276 ms |
93816 KB |
Output is correct |
| 2 |
Correct |
480 ms |
102064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
991 ms |
124912 KB |
Output is correct |
| 2 |
Runtime error |
3294 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1912 ms |
169080 KB |
Output is correct |
| 2 |
Runtime error |
3599 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3108 ms |
210556 KB |
Output is correct |
| 2 |
Runtime error |
3597 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3494 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3860 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3789 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
205 ms |
159212 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
207 ms |
159340 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
225 ms |
161004 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
