#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
struct fenw {
int n;
ve<ve<int>> que;
ve<ve<int>> fe;
fenw(int s) : n(s + 10) { que.resize(n); fe.resize(n); }
inline void pupd(int x, int y) { x += 3; for (; x < n; x += x & -x) que[x].pb(y); }
inline void pget(int x, int y) { if(x<0||y<0){return;} x += 3; for (; x; x -= x & -x) que[x].pb(y); }
inline void pget(int x0, int x1, int y0, int y1) {
if (x0 > x1 || y0 > y1) return;
pget(x1, y1);
pget(x0 - 1, y1);
pget(x1, y0 - 1);
pget(x0 - 1, y0 - 1);
}
inline void prep() {
for (int i = 0; i < n; ++i) {
sort(all(que[i]));
que[i].erase(unique(all(que[i])), que[i].end());
fe[i].resize(sz(que[i]) + 10);
}
}
inline void upd(int x, int y, int d) {
x += 3;
for (; x < n; x += x & -x) {
int i = lower_bound(all(que[x]), y) - que[x].begin() + 3;
for (; i < sz(fe[x]); i += i & -i) fe[x][i] += d;
}
}
inline int get(int x, int y) {
if (x < 0 || y < 0) return 0;
x += 3; int ans = 0;
for (; x; x -= x & -x) {
int i = lower_bound(all(que[x]), y) - que[x].begin() + 3;
for (; i; i -= i & -i) ans += fe[x][i];
} return ans;
}
inline int get(int x0, int x1, int y0, int y1) {
if (x0 > x1 || y0 > y1) return 0;
return get(x1, y1) - get(x0 - 1, y1) - get(x1, y0 - 1) + get(x0 - 1, y0 - 1);
}
};
struct fenw1d {
int n;
ve<int> fe;
fenw1d(int s) : n(s + 10) { fe.resize(n); }
inline void upd(int i, int x) { i += 3; for (; i < n; i += i & -i) fe[i] += x; }
inline int get(int i) { i += 3; int ans = 0; for (; i; i -= i & -i){ans+=fe[i];} return ans; }
inline int get(int l, int r) { if(l>r){return 0;} return get(r) - get(l - 1); }
};
inline void solve() {
int n;
cin >> n;
ve<array<int,4>> a(n);
for (auto &[a, b, c, d] : a) cin >> a >> b >> c >> d;
ve<int> alx, aly;
for (int i = 0; i < n; ++i) {
auto &[x, y, dx, dy] = a[i];
int x0 = x, x1 = x + dx - 1;
int y0 = y, y1 = y + dy - 1;
alx.pb(x0), alx.pb(x1);
aly.pb(y0), aly.pb(y1);
}
sort(all(alx)), sort(all(aly));
alx.erase(unique(all(alx)), alx.end());
aly.erase(unique(all(aly)), aly.end());
int m = sz(alx), my = sz(aly);
for (int i = 0; i < n; ++i) {
auto &[x, y, dx, dy] = a[i];
int x0 = x, x1 = x + dx - 1;
int y0 = y, y1 = y + dy - 1;
x0 = lower_bound(all(alx), x0) - alx.begin();
x1 = lower_bound(all(alx), x1) - alx.begin();
y0 = lower_bound(all(aly), y0) - aly.begin();
y1 = lower_bound(all(aly), y1) - aly.begin();
a[i] = {x0, y0, x1, y1};
}
fenw right_down(m);
fenw left_down(m);
fenw right_up(m);
fenw left_up(m);
fenw1d left(my);
fenw1d right(my);
fenw1d up(m);
fenw1d down(m);
reverse(all(a));
for (auto &[x0, y0, x1, y1] : a) {
right_down.pupd(x1, y1);
left_down.pupd(x1, y0);
right_up.pupd(x0, y1);
left_up.pupd(x0, y0);
right_down.pget(x0 - 1, y0 - 1);
left_up.pget(x1 + 1, m - 1, y1 + 1, my - 1);
right_up.pget(x1 + 1, m - 1, 0, y0 - 1);
left_down.pget(0, x0 - 1, y1 + 1, my - 1);
}
right_down.prep();
left_down.prep();
right_up.prep();
left_up.prep();
ve<int> res(n); int ptr = n - 1, cnt = 0;
for (auto &[x0, y0, x1, y1] : a) {
right_down.upd(x1, y1, +1);
left_down.upd(x1, y0, +1);
right_up.upd(x0, y1, +1);
left_up.upd(x0, y0, +1);
right.upd(y1, +1);
left.upd(y0, +1);
down.upd(x1, +1);
up.upd(x0, +1);
int ans = 0;
ans += right.get(y0 - 1);
ans += left.get(y1 + 1, my - 1);
ans += down.get(x0 - 1);
ans += up.get(x1 + 1, m - 1);
ans -= right_down.get(x0 - 1, y0 - 1);
ans -= left_up.get(x1 + 1, m - 1, y1 + 1, my - 1);
ans -= right_up.get(x1 + 1, m - 1, 0, y0 - 1);
ans -= left_down.get(0, x0 - 1, y1 + 1, my - 1);
res[ptr--] = (ans == cnt), ++cnt;
}
for (auto &i : res) cout << (i ? "DA" : "NE") << '\n';
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
/**
5
1 1 4 2
6 1 1 1
2 2 2 3
3 4 3 2
4 0 1 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
8916 KB |
Output is correct |
| 2 |
Correct |
112 ms |
12688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
22180 KB |
Output is correct |
| 2 |
Correct |
1332 ms |
88224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
563 ms |
42220 KB |
Output is correct |
| 2 |
Correct |
1849 ms |
107428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
802 ms |
57248 KB |
Output is correct |
| 2 |
Correct |
1355 ms |
88092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1567 ms |
94804 KB |
Output is correct |
| 2 |
Correct |
1912 ms |
115280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1565 ms |
97628 KB |
Output is correct |
| 2 |
Correct |
1732 ms |
106772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1437 ms |
94584 KB |
Output is correct |
| 2 |
Correct |
2284 ms |
127412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2392 ms |
141400 KB |
Output is correct |
| 2 |
Correct |
1691 ms |
103964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2951 ms |
151536 KB |
Output is correct |
| 2 |
Correct |
2732 ms |
155672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3597 ms |
191920 KB |
Output is correct |
| 2 |
Correct |
3391 ms |
192692 KB |
Output is correct |
