#include <bits/stdc++.h>
using namespace std;
typedef struct node* pnode;
const int MAXN = 2*1e5 + 10;
struct node{
pnode l,r;
bool some_colored,all_colored;
node(){
l = r = NULL;
some_colored = all_colored = false;
}
void update(int left,int right,int i,int j){
if(all_colored) return; // nothing to do here
// Interval is contained
if(left >= i && right <= j){
some_colored = true;
all_colored = true;
return;
}
int mid = (left+right)/2;
some_colored = true;
if(j <= mid){
if(!l) l = new node();
l->update(left,mid,i,j);
}
else if(i >= mid + 1){
if(!r) r = new node();
r->update(mid+1,right,i,j);
}
else{
if(!l) l = new node();
l->update(left,mid,i,j);
if(!r) r = new node();
r->update(mid+1,right,i,j);
}
}
bool query(int left,int right,int i,int j){
if(left >= i && right <= j) return some_colored;
if(all_colored) return all_colored;
if(!some_colored) return some_colored;
int mid = (left+right)/2;
if(j <= mid){
return (l ? l->query(left,mid,i,j) : false);
}
else if(i >= mid + 1){
return (r ? r->query(mid+1,right,i,j) : false);
}
else{
return (l ? l->query(left,mid,i,j) : false) || (r ? r->query(mid+1,right,i,j) : false);
}
}
};
vector<int> compx,compy;
bool isCovered[MAXN];
int N,szY,szX,X1[MAXN],X2[MAXN],Y1[MAXN],Y2[MAXN];
pnode seg_some[2*MAXN],seg_all[2*MAXN];
void update(int pos,int left,int right,int ix,int jx,int iy,int jy){
// Interval is contained
if(left >= ix && right <= jx){
if(!seg_some[pos]) seg_some[pos] = new node();
if(!seg_all[pos]) seg_all[pos] = new node();
seg_some[pos]->update(1,szY,iy,jy);
seg_all[pos]->update(1,szY,iy,jy);
return;
}
int mid = (left+right)/2;
if(!seg_some[pos]) seg_some[pos] = new node();
seg_some[pos]->update(1,szY,iy,jy);
if(jx <= mid){
update(2*pos,left,mid,ix,jx,iy,jy);
}
else if(ix >= mid + 1){
update(2*pos+1,mid+1,right,ix,jx,iy,jy);
}
else{
update(2*pos,left,mid,ix,jx,iy,jy);
update(2*pos+1,mid+1,right,ix,jx,iy,jy);
}
}
bool query(int pos,int left,int right,int ix,int jx,int iy,int jy){
if(left >= ix && right <= jx){
return (seg_some[pos] ? seg_some[pos]->query(1,szY,iy,jy) : false);
}
if(seg_all[pos] && seg_all[pos]->query(1,szY,iy,jy)) return true;
int mid = (left+right)/2;
if(jx <= mid){
return query(2*pos,left,mid,ix,jx,iy,jy);
}
else if(ix >= mid + 1){
return query(2*pos+1,mid+1,right,ix,jx,iy,jy);
}
else{
return query(2*pos,left,mid,ix,jx,iy,jy) || query(2*pos+1,mid+1,right,ix,jx,iy,jy);
}
}
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--){
isCovered[i] = query(1,1,szX,X1[i],X2[i]-1,Y1[i],Y2[i]-1);
update(1,1,szX,X1[i],X2[i]-1,Y1[i],Y2[i]-1);
}
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:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
~~~~~^~~~~~~~~
suncanje.cpp:131: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 |
Correct |
95 ms |
36984 KB |
Output is correct |
| 2 |
Correct |
138 ms |
53212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
293 ms |
116044 KB |
Output is correct |
| 2 |
Runtime error |
712 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
654 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
703 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 |
704 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 |
714 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 |
738 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 |
126 ms |
263168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
137 ms |
263168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
188 ms |
263168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
