#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 what
#define y2 chard
#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 140013
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;
ppp arr[MAXN];
vi xs, ys;
bitset<MAXN> ans;
vector<pair<pii, int> > ql[MAXN], qr[MAXN], del[MAXN], ins[MAXN];
int lazy[4 * MAXN];
pii stor[4 * MAXN];
set<pair<pii, int> > fw, bw;
pii comb(pii a, pii b)
{
if (a.fi < b.fi) return a;
if (a.fi > b.fi) return b;
return {a.fi, a.se + b.se};
}
void build(int w, int L, int R)
{
stor[w] = {0, R - L + 1};
lazy[w] = 0;
if (L == R) return;
int mid = (L + R) >> 1;
build(w << 1, L, mid);
build(w << 1 | 1, mid + 1, R);
}
void push(int w, int L, int R)
{
if (lazy[w] == 0);
stor[w].fi += lazy[w];
if (L != R)
{
lazy[w << 1] += lazy[w];
lazy[w << 1 | 1] += lazy[w];
}
lazy[w] = 0;
return;
}
void update(int w, int L, int R, int a, int b, int v)
{
// cerr << L << ' ' << R << ' ' << a << ' ' << b << ' ' << v << endl;
push(w, L, R);
if (b < L || R < a) return;
if (a <= L && R <= b)
{
lazy[w] += v;
push(w, L, R);
return;
}
int mid = (L + R) >> 1;
update(w << 1, L, mid, a, b, v);
update(w << 1 | 1, mid + 1, R, a, b, v);
stor[w] = comb(stor[w << 1], stor[w << 1 | 1]);
}
pii query(int w, int L, int R, int a, int b)
{
push(w, L, R);
if (a <= L && R <= b)
{
return stor[w];
}
int mid = (L + R) >> 1;
if (b <= mid) return query(w << 1, L, mid, a, b);
if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
return comb(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
}
void solve(int L, int R)
{
if (L == R) return;
int mid = (L + R) >> 1;
solve(L, mid);
solve(mid + 1, R);
// cerr << "SOLVE " << L << ' ' << R << endl;
xs.clear(); ys.clear();
FOR(i, L, R + 1)
{
xs.PB(arr[i].fi.fi); ys.PB(arr[i].fi.se); xs.PB(arr[i].se.fi); ys.PB(arr[i].se.se);
}
// cerr << SZ(xs) << ' ' << SZ(ys) << endl;
sort(ALL(xs)); xs.erase(unique(ALL(xs)), xs.end());
sort(ALL(ys)); ys.erase(unique(ALL(ys)), ys.end());
// cerr << SZ(xs) << ' ' << SZ(ys) << endl;
FOR(i, 0, SZ(xs))
{
ql[i].clear(); qr[i].clear(); ins[i].clear(); del[i].clear();
}
FOR(i, L, mid + 1)
{
int x1 = LB(ALL(xs), arr[i].fi.fi) - xs.begin();
int y1 = LB(ALL(ys), arr[i].fi.se) - ys.begin();
int x2 = LB(ALL(xs), arr[i].se.fi) - xs.begin() - 1;
int y2 = LB(ALL(ys), arr[i].se.se) - ys.begin() - 1;
ql[x1].PB({{y1, y2}, i});
qr[x2].PB({{y1, y2}, i});
// cerr << x2 << " WITHIN " << SZ(xs) << endl;
// cerr << "query " << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
//these are the guys that query.
}
FOR(i, mid + 1, R + 1)
{
int x1 = LB(ALL(xs), arr[i].fi.fi) - xs.begin();
int y1 = LB(ALL(ys), arr[i].fi.se) - ys.begin();
int x2 = LB(ALL(xs), arr[i].se.fi) - xs.begin() - 1;
int y2 = LB(ALL(ys), arr[i].se.se) - ys.begin() - 1;
ins[x1].PB({{y1, y2}, i});
del[x2].PB({{y1, y2}, i});
// cerr << "send " << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
//these are the guys that send.
}
build(1, 0, SZ(ys) - 1);
FOR(i, 0, SZ(xs))
{
// cerr << "YES\n";
// cerr << SZ(ins[i]) << endl;
for (auto a : ins[i])
{
// cerr << "ALIVE\n";
// cerr << "KILLER " << a.fi.fi << ' ' << a.fi.se << endl;
update(1, 0, SZ(ys) - 1, a.fi.fi, a.fi.se, 1);
int lo = a.fi.fi, hi = a.fi.se;
auto it = fw.LB({{lo, -1}, -1});
while(it != fw.end() && it -> fi.fi <= hi)
{
// cerr << it -> fi.fi << endl;
ans[it -> se] = true;
bw.erase({{it -> fi.se, it -> fi.fi}, it -> se});
it = fw.erase(it);
}
auto jt = bw.LB({{hi + 1, -1}, -1});
while(jt != bw.begin() && (prev(jt) -> fi.fi >= lo))
{
jt = prev(jt);
ans[jt -> se] = true;
bw.erase({{jt -> fi.se, jt -> fi.fi}, jt -> se});
jt = bw.erase(jt);
}
}
for (auto a : ql[i])
{
int idx = a.se;
pii p = query(1, 0, SZ(ys) - 1, a.fi.fi, a.fi.se);
if (p.fi != 0 || p.se != (a.fi.se - a.fi.fi + 1))
{
ans[idx] = true;
}
fw.insert({a.fi, idx});
bw.insert({{a.fi.se, a.fi.fi}, idx});
}
for (auto a : qr[i])
{
int idx = a.se;
pii p = query(1, 0, SZ(ys) - 1, a.fi.fi, a.fi.se);
if (p.fi != 0 || p.se != (a.fi.se - a.fi.fi + 1))
{
ans[idx] = true;
}
if (fw.find(a) != fw.end())
{
fw.erase({a.fi, idx});
bw.erase({{a.fi.se, a.fi.fi}, idx});
}
}
for (auto a : del[i])
{
update(1, 0, SZ(ys) - 1, a.fi.fi, a.fi.se, -1);
}
}
//either it overlaps on the left, or it overlaps on the right, or it is completely contained
//use the print segtree to solve the noraml case.
//otherwise the killer has to be inside the query.
//then we have a bunc hof query rectangles, and then
//so when you have a killer rectangle become alive, you just use the set.
}
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);
}
//update this rectangle.
//ehh seems hard.
//update r5 with 5. then update r4 with 4. then update r3 with 3.
//then if any point in rect x is updated with > x then you lose.
//OR
//in decreasing order of rectangles, update every point in a rectangle by 1.
//then for a given rectangle, query if there's anything on in it.
//bleh, you can like, store ranges of ok guys.
//the ndoe in the segtree stores, THERE'S AT LEAST ONE GUY IN HERE WITH THIS.
//then when you update x you don't even need to worry about its children.
solve(0, N - 1);
FOR(i, 0, N)
{
cout << (ans[i] ? "NE" : "DA") << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
14964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
211 ms |
16620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
423 ms |
19436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
621 ms |
21148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
985 ms |
26068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1059 ms |
26344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
976 ms |
26236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1336 ms |
53360 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 |
1631 ms |
54644 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 |
2085 ms |
59388 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
