/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author
*/
#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
struct Fenwick {
vector<int> f;
Fenwick() {}
Fenwick(int n) {
f.resize(n + 10);
}
void update(int i, int v) {
++i;
while(i < f.size()) f[i] += v, i += i & -i;
}
int query(int i) {
++i;
int ret = 0;
while(i > 0) ret += f[i], i -= i & -i;
return ret;
}
};
struct MST {
int n;
vector<vector<int> > ls;
vector<Fenwick> t;
MST() {}
MST(int n): n(n) {
ls.resize(4*n);
t.resize(4*n);
}
void clear() {
t.clear();
t = vector<Fenwick>(4*n);
}
void add_value(int x, int y) {
for(x += n; x >= 1; x >>= 1) ls[x].push_back(y);
}
// void build(int i, int l, int r) {
// cout << i << ' ' << l << ' ' << r << ' ' << ls[i].size() << ' ' << 2*n << endl;
// sort(ls[i].begin(), ls[i].end());
// ls[i].resize(unique(ls[i].begin(), ls[i].end()) - ls[i].begin());
// t[i] = Fenwick(ls[i].size());
// if(l == r) return;
// int mid = l+r >> 1;
// build(i << 1, l, mid);
// build(i << 1 | 1, mid+1, r);
// }
void build() {
for(int i = 2*n-1; i >= 1; i--) {
sort(ls[i].begin(), ls[i].end());
ls[i].resize(unique(ls[i].begin(), ls[i].end()) - ls[i].begin());
t[i] = Fenwick(ls[i].size());
}
}
void update(int x, int y) {
for(x += n; x >= 1; x >>= 1) {
auto it = lower_bound(ls[x].begin(), ls[x].end(), y);
assert(it != ls[x].end());
t[x].update(it - ls[x].begin(), 1);
}
}
int query(int x1, int y1, int x2, int y2) {
int ret = 0;
for(x1 += n, x2 += n+1; x1 < x2; x1 >>= 1, x2 >>= 1) {
if(x1 & 1) {
auto ity1 = lower_bound(ls[x1].begin(), ls[x1].end(), y1);
auto ity2 = upper_bound(ls[x1].begin(), ls[x1].end(), y2);
// cout << ity2 - ity1 << ' ' << y1 << ' ' << y2 << ' ' << t[x1].query(t[x1].f.size() - 2) << endl;
if(!ls[x1].empty() && ity1 != ls[x1].end() && ity2 != ls[x1].begin()) {
--ity2;
--ity1;
assert(!t[x1].f.empty());
ret += t[x1].query(ity2 - ls[x1].begin()) - t[x1].query(ity1 - ls[x1].begin());
}
++x1;
}
if(x2 & 1) {
--x2;
auto ity1 = lower_bound(ls[x2].begin(), ls[x2].end(), y1);
auto ity2 = upper_bound(ls[x2].begin(), ls[x2].end(), y2);
// cout << ity2 - ity1 << ' ' << y1 << ' ' << y2 << ' ' << t[x2].query(t[x2].f.size() - 2) << endl;
if(!ls[x2].empty() && ity1 != ls[x2].end() && ity2 != ls[x2].begin()) {
--ity2;
--ity1;
assert(!t[x2].f.empty());
ret += t[x2].query(ity2 - ls[x2].begin()) - t[x2].query(ity1 - ls[x2].begin());
}
}
}
return ret;
}
};
class Suncanje {
int n;
vector<tuple<int,int,int,int> > a;
vector<int> res;
vector<string> ans;
MST mst[4];
Fenwick fen[4];
vector<int> xs, ys;
void compress() {
for(int i = 0, x1, y1, x2, y2; i < n; i++) {
tie(x1, y1, x2, y2) = a[i];
xs.push_back(x1);
xs.push_back(x2);
ys.push_back(y1);
ys.push_back(y2);
}
sort(xs.begin(), xs.end());
xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
sort(ys.begin(), ys.end());
ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
// for(int x: xs) cout << x << ' ';
// cout << endl;
// for(int y: ys) cout << y << ' ';
// cout << endl;
for(auto &tt: a) {
int x1, y1, x2, y2;
tie(x1, y1, x2, y2) = tt;
auto it = lower_bound(xs.begin(), xs.end(), x1);
get<0>(tt) = it - xs.begin();
it = lower_bound(xs.begin(), xs.end(), x2);
get<2>(tt) = it - xs.begin();
it = lower_bound(ys.begin(), ys.end(), y1);
get<1>(tt) = it - ys.begin();
it = lower_bound(ys.begin(), ys.end(), y2);
get<3>(tt) = it - ys.begin();
// cout << x1 << ' ' << y1 << ' ' <<x2 << ' ' << y2 << endl;
}
// for(auto &tt: a) {
// int x1, y1, x2, y2;
// tie(x1, y1, x2, y2) = tt;
// cout << x1 << ' ' << y1 << ' ' <<x2 << ' ' << y2 << endl;
// }
}
public:
void solve(istream &cin, ostream &cout) {
cin >> n;
for(int i = 0, x1, y1, A, B; i < n; i++) {
cin >> x1 >> y1 >> A >> B;
a.emplace_back(x1, y1, x1 + A, y1 + B);
}
res.resize(n);
compress();
reverse(a.begin(), a.end());
int sz = max(xs.size(), ys.size());
for(int i = 0; i < 4; i++) {
mst[i] = MST(sz);
fen[i] = Fenwick(sz);
}
for(auto tt: a) {
int x1, y1, x2, y2;
tie(x1, y1, x2, y2) = tt;
mst[0].add_value(x1, y1);
mst[1].add_value(x1, y2);
mst[2].add_value(x2, y1);
mst[3].add_value(x2, y2);
}
for(int i = 0; i < 4; i++) mst[i].build();
for(int i = 0; i < n; i++) {
int x1, y1, x2, y2;
tie(x1, y1, x2, y2) = a[i];
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
int pos = 0, neg = 0;
pos += fen[2].query(x1) + i - fen[0].query(x2 - 1);
pos += fen[3].query(y1) + i - fen[1].query(y2 - 1);
neg += mst[0].query(x2, y2, sz - 1, sz - 1);
neg += mst[1].query(x2, 0, sz - 1, y1);
neg += mst[2].query(0, y2, x1, sz - 1);
neg += mst[3].query(0, 0, x1, y1);
res[i] = pos - neg;
// cout << n-i << ' ' << pos << ' ' << neg << ' ' << res[i] << endl;
// cout << fen[2].query(x1) << ' ' << fen[0].query(x2 - 1) << endl;
// cout << fen[3].query(y1) << ' ' << fen[1].query(y2 - 1) << endl;
fen[0].update(x1, 1);
fen[1].update(y1, 1);
fen[2].update(x2, 1);
fen[3].update(y2, 1);
mst[0].update(x1, y1);
mst[1].update(x1, y2);
mst[2].update(x2, y1);
mst[3].update(x2, y2);
ans.push_back((res[i] == i ? "DA" : "NE"));
}
reverse(ans.begin(), ans.end());
for(string s: ans) cout << s << '\n';
}
};
class Solver {
public:
void solve(std::istream& in, std::ostream& out) {
Suncanje *obj = new Suncanje();
obj->solve(in, out);
delete obj;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solver solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
Compilation message
suncanje.cpp: In member function 'void Fenwick::update(int, int)':
suncanje.cpp:23:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < f.size()) f[i] += v, i += i & -i;
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
17144 KB |
Output is correct |
| 2 |
Correct |
186 ms |
23656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
385 ms |
41856 KB |
Output is correct |
| 2 |
Correct |
2164 ms |
153064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
826 ms |
75548 KB |
Output is correct |
| 2 |
Correct |
2381 ms |
188272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1128 ms |
105872 KB |
Output is correct |
| 2 |
Correct |
1883 ms |
157856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2048 ms |
166316 KB |
Output is correct |
| 2 |
Correct |
2584 ms |
202060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2173 ms |
171948 KB |
Output is correct |
| 2 |
Correct |
2684 ms |
188780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2527 ms |
170436 KB |
Output is correct |
| 2 |
Correct |
3277 ms |
221352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3387 ms |
251128 KB |
Output is correct |
| 2 |
Correct |
2378 ms |
178044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1132 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1261 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
