제출 #86957

#제출 시각아이디문제언어결과실행 시간메모리
86957IvanCSunčanje (COCI18_suncanje)C++17
13 / 130
820 ms263168 KiB
#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){ // 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; 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; }

컴파일 시 표준 에러 (stderr) 메시지

suncanje.cpp: In function 'int main()':
suncanje.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
suncanje.cpp:128: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...