#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5;
const int MAXM = 2e5;
bool active[MAXN];
bool covered[MAXN];
vector<int> add[MAXM];
vector<int> del[MAXM];
vector<int> xval;
vector<int> yval;
map<int, int> convx;
map<int, int> convy;
class stree {
public:
int lp, rp;
stree *l = nullptr;
stree *r = nullptr;
priority_queue<int> actvals;
priority_queue<int> actvals_contained;
priority_queue<int, vector<int>, greater<int>> uncovered;
priority_queue<int, vector<int>, greater<int>> uncovered_contained;
stree(int lv, int rv) {
lp = lv;
rp = rv;
if (lp < rp) {
int m = (lp+rp)/2;
l = new stree(lp, m);
r = new stree(m+1, rp);
}
}
int cur_mx(priority_queue<int> &pq) {
while (!pq.empty() && !active[pq.top()]) pq.pop();
if (pq.empty()) return -1;
return pq.top();
}
// int get_mx(int lv, int rv) {
// if (lp > rv || rp < lv) return -1;
// if (lp >= lv && rp <= rv) return cur_mx();
// return max(l->get_mx(lv, rv), r->get_mx(lv, rv));
// }
void cover(int v, priority_queue<int, vector<int>, greater<int>> &pq) {
while (!pq.empty() && (pq.top() < v || covered[pq.top()])) {
covered[pq.top()] = 1;
pq.pop();
}
}
void ins(int lv, int rv, int v) {
if (lp > rv || rp < lv) return;
if (lp >= lv && rp <= rv) {
cover(v, uncovered_contained);
if (cur_mx(actvals_contained) > v) covered[v] = 1;
actvals.push(v);
actvals_contained.push(v);
if (!covered[v]) {
uncovered.push(v);
uncovered_contained.push(v);
}
return;
}
cover(v, uncovered);
if (cur_mx(actvals) > v) covered[v] = 1;
else uncovered_contained.push(v);
actvals_contained.push(v);
l->ins(lv, rv, v); r->ins(lv, rv, v);
}
};
pii xs[MAXN];
pii ys[MAXN];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> xs[i].first >> ys[i].first >> xs[i].second >> ys[i].second;
xs[i].second += xs[i].first;
ys[i].second += ys[i].first-1;
xval.push_back(xs[i].first);
xval.push_back(xs[i].second);
yval.push_back(ys[i].first);
yval.push_back(ys[i].second);
}
sort(xval.begin(), xval.end());
sort(yval.begin(), yval.end());
for (int x: xval) {
if (convx.find(x) == convx.end()) convx[x] = convx.size();
}
for (int y: yval) {
if (convy.find(y) == convy.end()) convy[y] = convy.size();
}
for (int i = 0; i < n; i++) {
add[convx[xs[i].first]].push_back(i);
del[convx[xs[i].second]].push_back(i);
ys[i].first = convy[ys[i].first];
ys[i].second = convy[ys[i].second];
// cout << ys[i].first << " " << ys[i].second << "\n";
}
stree *tree = new stree(0, convy.size()-1);
for (int i = 0; i < convx.size(); i++) {
for (int v: del[i]) {
active[v] = 0;
}
for (int v: add[i]) {
tree->ins(ys[v].first, ys[v].second, v);
active[v] = 1;
}
}
for (int i = 0; i < n; i++) {
if (covered[i]) cout << "NE\n";
else cout << "DA\n";
}
}
Compilation message
suncanje.cpp: In function 'int main()':
suncanje.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i = 0; i < convx.size(); i++) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
16332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
25952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
148 ms |
38460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
211 ms |
50500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
363 ms |
75252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
378 ms |
76864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
383 ms |
79308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
599 ms |
110252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
681 ms |
116468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
905 ms |
139496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
