Submission #95830

#	Time	Username	Problem	Language	Result	Execution time	Memory
95830		KLPP	Sunčanje (COCI18_suncanje)	C++14	0 / 130	590 ms	263168 KiB

suncanje

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<stdio.h>
#include<set>
#include<map>
#include<stack>
using namespace std;
typedef long long int lld;
vector<lld> coord;
int find(lld x){
	int lo,hi;
	lo=0;
	hi=coord.size()-1;
	while(hi-lo>=0){
		int mid=(hi+lo)/2;
		if(coord[mid]==x)return mid;
		if(coord[mid]<x)lo=mid+1;
		else hi=mid-1;
	}
}
struct node{
	node *L,*R;
	bool B1,B2;
	int l,r;
};
void init(node *n,int l, int r){
	n->l=l;
	n->r=r;
	n->B1=false;
	n->B2=false;
}
void extend(node *n){
	if(!n->L){
		n->L=new node();
		n->R=new node();
		int mid=(n->l+n->r)/2;
		init(n->L,n->l,mid);
		init(n->R,mid+1,n->r);
	}
}
void insert(node *n,int x, int y){
	extend(n);
	//cout<<n->l<<" "<<n->r<<endl;
	if(y<n->l || n->r<x)return;
	n->B1=true;
	if(x<=n->l && n->r<=y){
		n->B2=true;
		return;
	}//cout<<n->l<<" "<<n->r<<endl;
	insert(n->L,x,y);insert(n->R,x,y);
}
bool q(node *n,int x, int y){
	extend(n);
	if(y<n->l || n->r<x)return false;
	if(n->B2)return true;
	if(x<=n->l && n->r<=y){
		return n->B1;
	}
	return q(n->L,x,y)|q(n->R,x,y);
}
struct node2{
	node2 *L,*R;
	int l1,r1;
	int l2,r2;
	node *n1,*n2;
};
void init(node2 *n, int l1, int r1, int l2,int r2){
	n->l1=l1;
	n->l2=l2;
	n->r1=r1;
	n->r2=r2;
	n->n1=new node();
	init(n->n1,l2,r2);
	n->n2=new node();
	init(n->n2,l2,r2);
}
void extend(node2 *n){
	if(!n->L){
		n->L=new node2();
		n->R=new node2();
		int mid=(n->l1+n->r1)/2;
		init(n->L,n->l1,mid,n->l2,n->r2);
		init(n->R,mid+1,n->r1,n->l2,n->r2);	
	}
}
void insert(node2 *n, int x1, int y1, int x2, int y2){
	extend(n);
	if(y1<n->l1 || n->r1<x1)return;
	insert(n->n1,x2,y2);
	if(x1<=n->l1 && n->r1<=y1){
		insert(n->n2,x2,y2);
		return;
	}
	insert(n->L,x1,y1,x2,y2);
	insert(n->R,x1,y1,x2,y2);
}
bool q(node2 *n, int x1, int y1, int x2, int y2){
	//cout<<n->l1<<" "<<n->r1<<endl;
	extend(n);
	if(y1<n->l1 || n->r1<x1)return false;
	if(q(n->n2,x2,y2))return true;
	if(x1<=n->l1 && n->r1<=y1){
		return q(n->n1,x2,y2);
	}
	return q(n->L,x1,y1,x2,y2)|q(n->R,x1,y1,x2,y2);
}
int main(){
	int n;
	cin>>n;
	lld rect[n][4];
	for(int i=0;i<n;i++){
		for(int j=0;j<4;j++)cin>>rect[i][j];		
	}
	for(int i=0;i<n;i++){
		rect[i][2]+=rect[i][0]-1;
		rect[i][3]+=rect[i][1]-1;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<4;j++)coord.push_back(rect[i][j]);
	}
	sort(coord.begin(),coord.end());
	int cmp[n][4];
	for(int i=0;i<n;i++){
		for(int j=0;j<4;j++)cmp[i][j]=find(rect[i][j]);
	}
	/*for(int i=0;i<n;i++){
		for(int j=0;j<4;j++)cout<<cmp[i][j]<<" ";
		cout<<endl;
	}*/
	node2 *tree=new node2();
	init(tree,0,4*100000,0,4*100000);
	bool B[n];
	for(int i=n-1;i>-1;i--){
		bool b=q(tree,cmp[i][0],cmp[i][2],cmp[i][1],cmp[i][3]);
		insert(tree,cmp[i][0],cmp[i][2],cmp[i][1],cmp[i][3]);
		//cout<<b<<endl;
		B[i]=!b;
	}
	for(int i=0;i<n;i++){
		if(B[i])cout<<"DA"<<endl;
		else cout<<"NE"<<endl;
	}
	/*node2 *test=new node2();
	init(test,1,100000,1,100000);
	insert(test,1,100,1,100);
	cout<<q(test,100,200,100,200)<<endl;*/
	return 0;
}

Compilation message (stderr)

suncanje.cpp: In function 'int find(lld)':
suncanje.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13