#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
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>;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define y1 asdf
#define y2 ZXCV
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 530013
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pii, pii> ppp;
int N, M;
ppp arr[MAXN];
vi compress;
bitset<MAXN> ans;
set<pii> full[MAXN], part[MAXN];
bool trav(int w, int L, int R, int a, int b, pii p)
{
// cerr << "TRAV " << L << ' ' << R << ' ' << a << ' ' << b << endl;
bool res = false;
auto it = full[w].LB({p.fi, -1});
if (it != full[w].end() && it -> fi <= p.se) res = true;
if (it != full[w].begin() && (prev(it) -> se) >= p.fi) res = true;
if (a <= L && R <= b)
{
it = part[w].LB({p.fi, -1});
if (it != part[w].end() && it -> fi <= p.se) res = true;
if (it != part[w].begin() && (prev(it) -> se) >= p.fi) res = true;
}
//check with full[w]
//part[w] merges with p
int lt = p.fi, rt = p.se;
it = part[w].LB({p.fi, -1});
if (it != part[w].begin() && prev(it) -> se >= lt - 1)
{
it = prev(it); lt = it -> fi;
}
while(it != part[w].end() && it -> fi <= p.se + 1)
{
ckmax(rt, it -> se); it = part[w].erase(it);
}
part[w].insert({lt, rt});
if (a <= L && R <= b)
{
lt = p.fi; rt = p.se;
it = full[w].LB({p.fi, -1});
if (it != full[w].begin() && prev(it) -> se >= lt - 1)
{
it = prev(it); lt = it -> fi;
}
while(it != full[w].end() && it -> fi <= p.se + 1)
{
ckmax(rt, it -> se); it = full[w].erase(it);
}
full[w].insert({lt, rt});
return res;
//check with partial[w]
//full[w] merges with p
}
int mid = (L + R) >> 1;
if (a <= mid)
{
res |= trav(w << 1, L, mid, a, b, p);
}
if (mid < b)
{
res |= trav(w << 1 | 1, mid + 1, R, a, b, p);
}
return res;
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(4);
cin >> N;
FOR(i, 0, N)
{
cin >> arr[i].fi.fi >> arr[i].fi.se >> arr[i].se.fi >> arr[i].se.se;
arr[i].se.fi += (arr[i].fi.fi);
arr[i].se.se += (arr[i].fi.se - 1);
swap(arr[i].fi.se, arr[i].se.fi);
compress.PB(arr[i].fi.fi); compress.PB(arr[i].fi.se);
}
sort(ALL(compress)); compress.erase(unique(ALL(compress)), compress.end());
FOR(i, 0, N)
{
arr[i].fi.fi = LB(ALL(compress), arr[i].fi.fi) - compress.begin();
arr[i].fi.se = LB(ALL(compress), arr[i].fi.se) - compress.begin() - 1;
}
M = SZ(compress);
FORD(i, N, 0)
{
ans[i] = trav(1, 0, M - 1, arr[i].fi.fi, arr[i].fi.se, arr[i].se);
//so there's a full and a partial thing.
//a full is: it affects all the crap in ur child. this thing is a PART of ur range.
//a partial is: it affects evreything containing it. this thing shares something with ur range.
}
FOR(i, 0, N)
{
cout << (ans[i] ? "NE" : "DA") << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
53240 KB |
Output is correct |
| 2 |
Correct |
103 ms |
54776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
58232 KB |
Output is correct |
| 2 |
Correct |
687 ms |
89456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
270 ms |
63972 KB |
Output is correct |
| 2 |
Correct |
908 ms |
102380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
70524 KB |
Output is correct |
| 2 |
Correct |
777 ms |
94264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
760 ms |
89984 KB |
Output is correct |
| 2 |
Correct |
984 ms |
103640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
745 ms |
86680 KB |
Output is correct |
| 2 |
Correct |
1018 ms |
104820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
814 ms |
97780 KB |
Output is correct |
| 2 |
Correct |
898 ms |
91636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1295 ms |
122692 KB |
Output is correct |
| 2 |
Correct |
740 ms |
85464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1423 ms |
121024 KB |
Output is correct |
| 2 |
Correct |
1564 ms |
129804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1551 ms |
123872 KB |
Output is correct |
| 2 |
Correct |
2013 ms |
149612 KB |
Output is correct |
