#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);
}
};
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);
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, my - 1);
right_down.pget(m - 1, y0 - 1);
left_up.pget(0, m - 1, y1 + 1, my - 1);
left_up.pget(x1 + 1, m - 1, 0, my - 1);
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);
int ans = 0;
ans += right_down.get(x0 - 1, my - 1);
ans += right_down.get(m - 1, y0 - 1);
ans += left_up.get(0, m - 1, y1 + 1, my - 1);
ans += left_up.get(x1 + 1, m - 1, 0, my - 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 |
90 ms |
9652 KB |
Output is correct |
| 2 |
Correct |
158 ms |
14244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
286 ms |
23988 KB |
Output is correct |
| 2 |
Correct |
1729 ms |
101936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
742 ms |
47264 KB |
Output is correct |
| 2 |
Correct |
2245 ms |
123636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
983 ms |
62748 KB |
Output is correct |
| 2 |
Correct |
1767 ms |
99672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1919 ms |
106992 KB |
Output is correct |
| 2 |
Correct |
2418 ms |
132500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1892 ms |
109024 KB |
Output is correct |
| 2 |
Correct |
2192 ms |
121584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1774 ms |
104416 KB |
Output is correct |
| 2 |
Correct |
2832 ms |
147808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2837 ms |
157712 KB |
Output is correct |
| 2 |
Correct |
2159 ms |
120640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3183 ms |
169204 KB |
Output is correct |
| 2 |
Correct |
3316 ms |
175052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4050 ms |
216216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
