#ifdef _MSC_VER
#define __builtin_popcount (int)__popcnt
#define __builtin_popcountll (int)__popcnt64
#define __builtin_clz (int)__lzcnt
#define $ system("pause")
#else
#define $
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> point;
#define MOD ll(1e9 + 7)
#define MAXN int(2e5 + 20)
#define lg 17
#define inf int(2e9 + 100)
#define rep(i, j, k) for (int i = j; i < k; i++)
#define for_all(x) x.begin(), x.end()
#define lid id << 1
#define rid id << 1 | 1
#define lch l, mid, lid
#define rch mid, r, rid
#define pb push_back
#define X first
#define Y second
#define re real()
#define im imag()
template <typename S, typename T>
inline ostream &operator<<(ostream &out, const pair<S, T> &p)
{
return out << "( " << p.X << " , " << p.Y << " )";
}
template <typename S>
inline ostream &operator<<(ostream &out, const vector<S> &p)
{
for (auto &e : p) out << e << ' '; return out;
}
template <typename T, typename S> inline T
smin(T &a, const S &b) { return a > b ? a = b : a; }
template <typename T, typename S> inline T
smax(T &a, const S &b) { return a < b ? a = b : a; }
inline double dot(const point l, const point r) { return l.re * r.re + l.im * r.im; }
inline double cross(const point l, const point r) { return l.re * r.im - l.im * r.re; }
ll po(ll v, ll u) { return u ? (po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD) : 1; }
inline void add(ll &l, const ll &r) { l = (l + r) % MOD; }
ll gcd(ll v, ll u) { return u ? gcd(u, v % u) : v; }
int n, m;
int arr[MAXN], x[MAXN], y[MAXN], a[MAXN], b[MAXN];
bool answer[MAXN];
struct Segment {
set<pii> s;
inline set<pii>::iterator get_itr(int r) {
return s.lower_bound(pii(r, -100));
}
inline set<pii>::iterator get_itl(int l) {
auto itl = s.lower_bound(pii(l, -100));
if (itl != s.begin()) {
auto it2 = itl; it2--;
if ((*it2).Y > l)
itl = it2;
}
return itl;
}
inline bool merge(int l, int r) {
auto itr = get_itr(r);
auto itl = get_itl(l);
if (itl == itr) {
s.insert(pii(l, r));
return false;
}
smin(l, (*itl).X);
itr--;
smax(r, (*itr).Y);
itr++;
while (itl != itr) {
auto it = itl;
itl++;
s.erase(it);
}
s.insert(pii(l, r));
return true;
}
inline bool get(int l, int r) {
return get_itl(l) != get_itr(r);
}
} seg[MAXN * 4], seg2[MAXN * 4];
bool seg_add(int s, int t, int ss, int tt, int l = 0, int r = m, int id = 1) {
if (l >= t || r <= s) return false;
if (l >= s && r <= t) {
//cout << l << ' ' << r << endl;
return (seg[id].merge(ss, tt) || seg2[id].merge(ss, tt));
}
int mid = l + r >> 1;
seg2[id].merge(ss, tt);
return seg[id].get(ss, tt) || seg_add(s, t, ss, tt, lch) || seg_add(s, t, ss, tt, rch);
}
inline bool bad(int i, int j) {
int l = max(x[i], x[j]);
int r = min(x[i] + a[i], x[j] + a[j]);
if (r <= l) return false;
l = max(y[i], y[j]);
r = min(y[i] + b[i], y[j] + b[j]);
if (r <= l) return false;
return true;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
rep(i, 0, n) {
cin >> x[i] >> y[i] >> a[i] >> b[i];
arr[i << 1] = x[i] + 1;
arr[i << 1 | 1] = x[i] + a[i];
}
sort(arr, arr + 2 * n);
m = unique(arr, arr + 2 * n) - arr;
//rep(i, 0, n) rep(j, i + 1, n) answer[i] |= bad(i, j);
for (int i = n - 1; ~i; i--) {
int l = lower_bound(arr, arr + m, x[i] + 1) - arr;
int r = lower_bound(arr, arr + m, x[i] + a[i] + 1) - arr;
//cout << i << " : GO" << endl;
answer[i] = seg_add(l, r, y[i], y[i] + b[i]);
}
rep(i, 0, n)
cout << (answer[i] ? "NE\n" : "DA\n");
$;
return (0);
}
/*
4
0 0 1 2
0 4 1 2
0 1 1 4
0 3 1 10
*/
Compilation message
suncanje.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
suncanje.cpp:47:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (auto &e : p) out << e << ' '; return out;
^~~
suncanje.cpp:47:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (auto &e : p) out << e << ' '; return out;
^~~~~~
suncanje.cpp: In function 'bool seg_add(int, int, int, int, int, int, int)':
suncanje.cpp:106:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
111 ms |
78912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
172 ms |
83368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
268 ms |
88992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
371 ms |
94944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
945 ms |
117828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
762 ms |
117828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1231 ms |
131624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2055 ms |
157640 KB |
Output is correct |
| 2 |
Incorrect |
733 ms |
157640 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1874 ms |
157952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1845 ms |
160668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
