#include <bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
#define taskname "SUMCANJE"
using namespace std;
typedef long long ll;
typedef pair <int, int> ii;
const int N = 1e5 + 1;
const int INF = 1e9;
struct rectangle{
int x1, x2, y1, y2;
rectangle(int _x1 = 0, int _x2 = 0, int _y1 = 0, int _y2 = 0){
x1 = _x1;
x2 = _x2;
y1 = _y1;
y2 = _y2;
}
};
struct segmentTree{
set <ii> d[N * 8];
bool check(set <ii> &s, int l, int r){
if (s.empty())
return 1;
auto it = s.lower_bound(mp(l, 0));
if (it != s.end()){
if ((*it).X <= r)
return 0;
}
if (it != s.begin()){
--it;
if ((*it).Y >= l)
return 0;
}
return 1;
}
void add(set <ii> &s, int l, int r){
if (s.empty()){
s.insert(mp(l, r));
return;
}
auto first = s.upper_bound(mp(l, 0));
auto last = s.upper_bound(mp(r, INF));
if (first != s.begin()){
--first;
if ((*first).Y < l)
++first;
}
vector <ii> tmp;
while (first != last){
tmp.push_back(*first);
++first;
}
for(ii p : tmp){
s.erase(p);
l = min(l, p.X);
r = max(r, p.Y);
}
s.insert(mp(l, r));
}
bool addRect(int id, int l, int r, int x1, int x2, int y1, int y2){
if (x2 < l || r < x1)
return 1;
bool res = check(d[id], y1, y2);
if (x1 <= l && r <= x2){
add(d[id], y1, y2);
return res;
}
int mid = (l + r) >> 1;
res = res && addRect(id << 1, l, mid, x1, x2, y1, y2);
res = res && addRect(id << 1 | 1, mid + 1, r, x1, x2, y1, y2);
return res;
}
} ST;
int n;
rectangle rect[N];
int x[2 * N], nX, y[2 * N], nY;
bool ans[N];
void readInput(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
int x, y, a, b;
scanf("%d %d %d %d", &x, &y, &a, &b);
rect[i] = rectangle(x, x + a - 1, y, y + b - 1);
}
}
void prepare(){
for(int i = 1; i <= n; i++){
x[++nX] = rect[i].x1;
x[++nX] = rect[i].x2;
y[++nY] = rect[i].y1;
y[++nY] = rect[i].y2;
}
sort(x + 1, x + 1 + nX);
sort(y + 1, y + 1 + nY);
nX = unique(x + 1, x + 1 + nX) - (x + 1);
nY = unique(y + 1, y + 1 + nY) - (y + 1);
for(int i = 1; i <= n; i++){
rect[i].x1 = lower_bound(x + 1, x + 1 + nX, rect[i].x1) - x;
rect[i].x2 = lower_bound(x + 1, x + 1 + nX, rect[i].x2) - x;
rect[i].y1 = lower_bound(y + 1, y + 1 + nY, rect[i].y1) - y;
rect[i].y2 = lower_bound(y + 1, y + 1 + nY, rect[i].y2) - y;
}
}
void solve(){
for(int i = n; i >= 1; i--)
ans[i] = ST.addRect(1, 1, nX, rect[i].x1, rect[i].x2, rect[i].y1, rect[i].y2);
for(int i = 1; i <= n; i++)
if (ans[i])
printf("DA\n");
else
printf("NE\n");
}
int main(){
//freopen(taskname".inp", "r", stdin);
//freopen(taskname".out", "w", stdout);
readInput();
prepare();
solve();
return 0;
}
Compilation message
suncanje.cpp: In function 'void readInput()':
suncanje.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
92 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
suncanje.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
95 | scanf("%d %d %d %d", &x, &y, &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
40440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
41436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
43268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
112 ms |
44408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
50108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
198 ms |
48888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
51836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
392 ms |
57788 KB |
Output is correct |
| 2 |
Incorrect |
190 ms |
47992 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
423 ms |
57912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
456 ms |
58104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
