#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii; // retangulo, y1, y2, caso
const int MAXN = 2*1e5 + 10;
vector<int> compx,compy;
vector<ii> offline_trick[4*MAXN];
bool isCovered[MAXN];
int N,szY,szX,X1[MAXN],X2[MAXN],Y1[MAXN],Y2[MAXN];
int seg_some[4*MAXN][2],seg_all[4*MAXN][2],cur_iteration; // seg[][0] : some, seg[][1] : all
void build_tree(int pos,int left,int right,int ix,int jx,int idx){
// Interval is contained
if(left >= ix && right <= jx){
offline_trick[pos].push_back(ii(idx,1));
return;
}
int mid = (left+right)/2;
offline_trick[pos].push_back(ii(idx,0));
if(jx <= mid){
build_tree(2*pos,left,mid,ix,jx,idx);
}
else if(ix >= mid + 1){
build_tree(2*pos+1,mid+1,right,ix,jx,idx);
}
else{
build_tree(2*pos,left,mid,ix,jx,idx);
build_tree(2*pos+1,mid+1,right,ix,jx,idx);
}
}
void update(int pos,int left,int right,int i,int j,int tipo){
if(left >= i && right <= j){
seg_some[pos][0] = cur_iteration;
seg_some[pos][1] = cur_iteration;
if(tipo == 1){
seg_all[pos][0] = cur_iteration;
seg_all[pos][1] = cur_iteration;
}
return;
}
int mid = (left+right)/2;
seg_some[pos][0] = cur_iteration;
if(tipo == 1){
seg_some[pos][1] = cur_iteration;
}
if(j <= mid){
update(2*pos,left,mid,i,j,tipo);
}
else if(i >= mid + 1){
update(2*pos+1,mid+1,right,i,j,tipo);
}
else{
update(2*pos,left,mid,i,j,tipo);
update(2*pos+1,mid+1,right,i,j,tipo);
}
}
bool query(int pos,int left,int right,int i,int j,int tipo){
if(left >= i && right <= j){
if(seg_all[pos][0] == cur_iteration) return true;
if(tipo == 1 && seg_some[pos][0] == cur_iteration) return true;
return false;
}
int mid = (left+right)/2;
if(seg_all[pos][1] == cur_iteration) return true;
if(tipo == 1 && seg_some[pos][1] == cur_iteration) return true;
if(j <= mid){
return query(2*pos,left,mid,i,j,tipo);
}
else if(i >= mid + 1){
return query(2*pos+1,mid+1,right,i,j,tipo);
}
else{
return query(2*pos,left,mid,i,j,tipo) || query(2*pos+1,mid+1,right,i,j,tipo);
}
}
void processa(int segPos){
//printf("Aqui %d\n",segPos);
cur_iteration++;
for(ii u : offline_trick[segPos]){
int idx = u.first, tipo = u.second;
int y1 = Y1[idx],y2 = Y2[idx] - 1;
isCovered[idx] |= query(1,1,szY,y1,y2,tipo);
update(1,1,szY,y1,y2,tipo);
}
}
int main(){
scanf("%d",&N);
for(int i = 1;i<=N;i++){
int xi,yi,ai,bi;
scanf("%d %d %d %d",&xi,&yi,&ai,&bi);
X1[i] = xi;
X2[i] = xi + ai;
Y1[i] = yi;
Y2[i] = yi + bi;
compx.push_back(X1[i]);
compx.push_back(X2[i]);
compy.push_back(Y1[i]);
compy.push_back(Y2[i]);
}
sort(compx.begin(),compx.end());
compx.erase(unique(compx.begin(),compx.end()),compx.end());
sort(compy.begin(),compy.end());
compy.erase(unique(compy.begin(),compy.end()),compy.end());
szY = (int)compy.size();
szX = (int)compx.size();
for(int i = 1;i<=N;i++){
X1[i] = lower_bound(compx.begin(),compx.end(),X1[i]) - compx.begin() + 1;
X2[i] = lower_bound(compx.begin(),compx.end(),X2[i]) - compx.begin() + 1;
Y1[i] = lower_bound(compy.begin(),compy.end(),Y1[i]) - compy.begin() + 1;
Y2[i] = lower_bound(compy.begin(),compy.end(),Y2[i]) - compy.begin() + 1;
}
for(int i = N;i>=1;i--){
build_tree(1,1,szX,X1[i],X2[i]-1,i);
}
//printf("Buildo\n");
for(int i = 1;i<=4*szX;i++) processa(i);
for(int i = 1;i<=N;i++){
if(isCovered[i]) printf("NE\n");
else printf("DA\n");
}
return 0;
}
Compilation message
suncanje.cpp: In function 'int main()':
suncanje.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
~~~~~^~~~~~~~~
suncanje.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&xi,&yi,&ai,&bi);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
21112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
152 ms |
24528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
303 ms |
29488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
425 ms |
32192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
713 ms |
41336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
741 ms |
42232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
643 ms |
42232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1055 ms |
52480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1418 ms |
57140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1972 ms |
65344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
