#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define MOD ll(998244353)
using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
typedef short int si;
typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
void del(vector <int> &g)
{
sort(g.begin(), g.end());
g.resize(unique(g.begin(), g.end()) - g.begin());
}
struct st{
vector <int> g, fen;
int kol;
st() : kol(0), g(0), fen(0) {}
void build()
{
del(g);
fen.resize(sz(g));
}
void upd(int y)
{
int v = upper_bound(g.begin(), g.end(), y) - g.begin() - 1;
for (; v < sz(g); v = (v | (v + 1))) fen[v]++;
kol++;
}
int sm(int y)
{
int ans = 0;
int v = upper_bound(g.begin(), g.end(), y) - g.begin() - 1;
for (; v >= 0; v = (v & (v + 1)) - 1) ans += fen[v];
return ans;
}
};
ordered_set lf, rg, up, dw;
st t[4][N];
vector <int> x1, x2;
int calcer(int x, int y, int xr, int yr)
{
int kol = 0;
int v = upper_bound(x2.begin(), x2.end(), x) - x2.begin() - 1;
for (; v >= 0; v = (v & (v + 1)) - 1) kol += t[0][v].kol - t[0][v].sm(yr - 1);
v = upper_bound(x2.begin(), x2.end(), x) - x2.begin() - 1;
for (; v >= 0; v = (v & (v + 1)) - 1) kol += t[2][v].sm(y);
v = sz(x1) - (lower_bound(x1.begin(), x1.end(), xr) - x1.begin()) - 1;
for (; v >= 0; v = (v & (v + 1)) - 1) kol += t[1][v].kol - t[1][v].sm(yr - 1);
v = sz(x1) - (lower_bound(x1.begin(), x1.end(), xr) - x1.begin()) - 1;
for (; v >= 0; v = (v & (v + 1)) - 1) kol += t[3][v].sm(y);
return kol;
}
void add(int x, int y, int xr, int yr)
{
lf.insert(x);
rg.insert(xr);
up.insert(yr);
dw.insert(y);
int v = lower_bound(x2.begin(), x2.end(), xr) - x2.begin();
for (; v < sz(x2); v = (v | (v + 1))) t[0][v].upd(y);
v = lower_bound(x2.begin(), x2.end(), xr) - x2.begin();
for (; v < sz(x2); v = (v | (v + 1))) t[2][v].upd(yr);
v = sz(x1) - (lower_bound(x1.begin(), x1.end(), x) - x1.begin()) - 1;
for (; v < sz(x1); v = (v | (v + 1))) t[1][v].upd(y);
v = sz(x1) - (lower_bound(x1.begin(), x1.end(), x) - x1.begin()) - 1;
for (; v < sz(x1); v = (v | (v + 1))) t[3][v].upd(yr);
}
int calc(int x, int y, int xr, int yr)
{
int kol = 0;
kol += rg.order_of_key(x + 1);
kol += up.order_of_key(y + 1);
kol += sz(lf) - lf.order_of_key(xr);
kol += sz(dw) - dw.order_of_key(yr);
return kol;
}
int main()
{
// freopen("input.txt", "r", stdin);// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
int x[n], y[n], xr[n], yr[n];
for (int i = 0; i < n; i++)
{
cin >> x[i] >> y[i] >> xr[i] >> yr[i];
xr[i] += x[i];
yr[i] += y[i];
x1.pb(x[i]);
x2.pb(xr[i]);
}
del(x1); del(x2);
for (int i = 0; i < n; i++)
{
int v = lower_bound(x2.begin(), x2.end(), xr[i]) - x2.begin();
for (; v < sz(x2); v = (v | (v + 1))) t[0][v].g.pb(y[i]);
v = lower_bound(x2.begin(), x2.end(), xr[i]) - x2.begin();
for (; v < sz(x2); v = (v | (v + 1))) t[2][v].g.pb(yr[i]);
v = sz(x1) - (lower_bound(x1.begin(), x1.end(), x[i]) - x1.begin()) - 1;
for (; v < sz(x1); v = (v | (v + 1))) t[1][v].g.pb(y[i]);
v = sz(x1) - (lower_bound(x1.begin(), x1.end(), x[i]) - x1.begin()) - 1;
for (; v < sz(x1); v = (v | (v + 1))) t[3][v].g.pb(yr[i]);
}
for (int i = 0; i < sz(x1); i++) {t[1][i].build(); t[3][i].build();}
for (int i = 0; i < sz(x2); i++) {t[2][i].build(); t[0][i].build();}
bool ans[n];
for (int i = n - 1; i >= 0; i--)
{
int cx = x[i], cy = y[i], xc = xr[i], yc = yr[i];
int kol = calc(cx, cy, xc, yc);
kol -= calcer(cx, cy, xc, yc);
ans[i] = (kol == n - i - 1);
add(cx, cy, xc, yc);
}
for (int i = 0; i < n; i++) cout << (ans[i] ? "DA" : "NE") << '\n';
}
Compilation message
suncanje.cpp: In constructor 'st::st()':
suncanje.cpp:40:9: warning: 'st::kol' will be initialized after [-Wreorder]
int kol;
^~~
suncanje.cpp:38:18: warning: 'std::vector<int> st::g' [-Wreorder]
vector <int> g, fen;
^
suncanje.cpp:42:5: warning: when initialized here [-Wreorder]
st() : kol(0), g(0), fen(0) {}
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
25336 KB |
Output is correct |
| 2 |
Correct |
95 ms |
26748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
199 ms |
30200 KB |
Output is correct |
| 2 |
Correct |
985 ms |
53108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
415 ms |
36652 KB |
Output is correct |
| 2 |
Correct |
1295 ms |
60432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
626 ms |
42432 KB |
Output is correct |
| 2 |
Correct |
1030 ms |
54260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1124 ms |
54480 KB |
Output is correct |
| 2 |
Correct |
1429 ms |
63640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1216 ms |
56156 KB |
Output is correct |
| 2 |
Correct |
1392 ms |
61428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1202 ms |
55912 KB |
Output is correct |
| 2 |
Correct |
1663 ms |
67128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2056 ms |
72352 KB |
Output is correct |
| 2 |
Correct |
1323 ms |
58508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2257 ms |
77268 KB |
Output is correct |
| 2 |
Correct |
2220 ms |
80092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2738 ms |
88656 KB |
Output is correct |
| 2 |
Correct |
2862 ms |
94236 KB |
Output is correct |
