/**
* 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(2*n);
t.resize(2*n);
}
void clear() {
for(int i = 1; i < 2*n; i++) fill(t[i].f.begin(), t[i].f.end(), 0);
}
void add_value(int x, int y) {
for(x += n; x >= 1; x >>= 1) ls[x].push_back(y);
}
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;
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(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();
}
}
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++) fen[i] = Fenwick(sz);
mst = MST(sz);
for(auto tt: a) {
int x1, y1, x2, y2;
tie(x1, y1, x2, y2) = tt;
mst.add_value(x1, y1);
mst.add_value(x1, y2);
mst.add_value(x2, y1);
mst.add_value(x2, y2);
}
mst.build();
for(int i = 0; i < n; i++) {
int x1, y1, x2, y2;
tie(x1, y1, x2, y2) = a[i];
res[i] -= mst.query(x2, y2, sz - 1, sz - 1);
mst.update(x1, y1);
}
mst.clear();
for(int i = 0; i < n; i++) {
int x1, y1, x2, y2;
tie(x1, y1, x2, y2) = a[i];
res[i] -= mst.query(x2, 0, sz - 1, y1);
mst.update(x1, y2);
}
mst.clear();
for(int i = 0; i < n; i++) {
int x1, y1, x2, y2;
tie(x1, y1, x2, y2) = a[i];
res[i] -= mst.query(0, y2, x1, sz - 1);
mst.update(x2, y1);
}
mst.clear();
for(int i = 0; i < n; i++) {
int x1, y1, x2, y2;
tie(x1, y1, x2, y2) = a[i];
res[i] -= mst.query(0, 0, x1, y1);
mst.update(x2, y2);
}
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;
res[i] += fen[2].query(x1) + i - fen[0].query(x2 - 1);
res[i] += 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);
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 |
73 ms |
5368 KB |
Output is correct |
| 2 |
Correct |
132 ms |
7328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
247 ms |
12916 KB |
Output is correct |
| 2 |
Correct |
1508 ms |
47352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
536 ms |
23480 KB |
Output is correct |
| 2 |
Correct |
1782 ms |
58480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
957 ms |
32876 KB |
Output is correct |
| 2 |
Correct |
1418 ms |
49536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1654 ms |
53072 KB |
Output is correct |
| 2 |
Correct |
2377 ms |
63384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2060 ms |
54720 KB |
Output is correct |
| 2 |
Correct |
1896 ms |
60772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1871 ms |
53336 KB |
Output is correct |
| 2 |
Correct |
2623 ms |
70380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2806 ms |
79852 KB |
Output is correct |
| 2 |
Correct |
2045 ms |
56040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3576 ms |
90888 KB |
Output is correct |
| 2 |
Correct |
3481 ms |
91608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4027 ms |
105940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
