oj.uz

Submission #86961

# Submission time Handle Problem Language Result Execution time Memory
86961 2018-11-28T22:35:59 Z IvanC Sunčanje (COCI18_suncanje) C++17
130 / 130
 2015 ms 73196 KB 
#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_some(int pos,int left,int right,int i,int j){

	if(left >= i && right <= j){
		seg_some[pos][0] = cur_iteration;
		seg_some[pos][1] = cur_iteration;
		return;
	}

	int mid = (left+right)/2;
	seg_some[pos][0] = cur_iteration;

	if(j <= mid){
		update_some(2*pos,left,mid,i,j);
	}
	else if(i >= mid + 1){
		update_some(2*pos+1,mid+1,right,i,j);
	}
	else{
		update_some(2*pos,left,mid,i,j);
		update_some(2*pos+1,mid+1,right,i,j);
	}

}

void update_all(int pos,int left,int right,int i,int j){

	if(left >= i && right <= j){
		seg_all[pos][0] = cur_iteration;
		seg_all[pos][1] = cur_iteration;
		return;
	}

	int mid = (left+right)/2;
	seg_all[pos][0] = cur_iteration;

	if(j <= mid){
		update_all(2*pos,left,mid,i,j);
	}
	else if(i >= mid + 1){
		update_all(2*pos+1,mid+1,right,i,j);
	}
	else{
		update_all(2*pos,left,mid,i,j);
		update_all(2*pos+1,mid+1,right,i,j);
	}

}

bool query_some(int pos,int left,int right,int i,int j){

	if(left >= i && right <= j) return seg_some[pos][0] == cur_iteration;
	if(seg_some[pos][1] == cur_iteration) return true;

	int mid = (left+right)/2;

	if(j <= mid) return query_some(2*pos,left,mid,i,j);
	else if(i >= mid + 1) return query_some(2*pos+1,mid+1,right,i,j);
	else return query_some(2*pos,left,mid,i,j) || query_some(2*pos+1,mid+1,right,i,j);

}

bool query_all(int pos,int left,int right,int i,int j){

	if(left >= i && right <= j) return seg_all[pos][0] == cur_iteration;
	if(seg_all[pos][1] == cur_iteration) return true;

	int mid = (left+right)/2;

	if(j <= mid) return query_all(2*pos,left,mid,i,j);
	else if(i >= mid + 1) return query_all(2*pos+1,mid+1,right,i,j);
	else return query_all(2*pos,left,mid,i,j) || query_all(2*pos+1,mid+1,right,i,j);

}

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;
		if(tipo == 0){
			isCovered[idx] |= query_all(1,1,szY,y1,y2);
			update_some(1,1,szY,y1,y2);
		}
		else{
			isCovered[idx] |= query_some(1,1,szY,y1,y2);
			update_some(1,1,szY,y1,y2);
			update_all(1,1,szY,y1,y2);
		}
	}

}

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:135:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
suncanje.cpp:138: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

# Verdict Execution time Memory Grader output
1 Correct 66 ms 21112 KB Output is correct
2 Correct 82 ms 21884 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 24656 KB Output is correct
2 Correct 653 ms 37976 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 37976 KB Output is correct
2 Correct 839 ms 41788 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 41788 KB Output is correct
2 Correct 691 ms 41788 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 41788 KB Output is correct
2 Correct 912 ms 43908 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 885 ms 43908 KB Output is correct
2 Correct 973 ms 43908 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 43908 KB Output is correct
2 Correct 1211 ms 49500 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1156 ms 54656 KB Output is correct
2 Correct 908 ms 54656 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1521 ms 61064 KB Output is correct
2 Correct 1443 ms 62836 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2015 ms 71696 KB Output is correct
2 Correct 1838 ms 73196 KB Output is correct