oj.uz

답안 #86957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
86957 2018-11-28T17:55:52 Z IvanC Sunčanje (COCI18_suncanje) C++17
13 / 130
 820 ms 263168 KB 
#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;
}

Compilation message

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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 45436 KB Output is correct
2 Correct 227 ms 62580 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 458 ms 159832 KB Output is correct
2 Runtime error 808 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 820 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 760 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 764 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 772 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 814 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 129 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 153 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 175 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -