Submission #330726

#	Time	Username	Problem	Language	Result	Execution time	Memory
330726		tzxydby	Plahte (COCI17_plahte)	C++11	64 / 160	999 ms	333400 KiB

plahte

#include<bits/stdc++.h>
using namespace std;
const int N=80005,M=30000000;
struct sq
{
	int x1,x2,y1,y2,id;
	bool operator<(const sq &k)const
	{
		return 1ll*(x2-x1)*(y2-y1)>1ll*(k.x2-k.x1)*(k.y2-k.y1);
	}
}a[N];
int n,m,sz,sx,sy,mx[M],lc[M],rc[M],qx[N],qy[N],qt[N],ans[N],vis[N];
vector<int>vx,vy,e[N];
set<int>s[N];
struct seg
{
	int rt;
	int xd()
	{
		sz++;
		return sz;
	}
	void update(int &k,int l,int r,int a,int b,int v)
	{
		if(!k) k=xd();
		if(l==a&&r==b)
		{
			mx[k]=max(mx[k],v);
			return;
		}
		int mid=l+r>>1;
		if(b<=mid) update(lc[k],l,mid,a,b,v);
		else if(a>mid) update(rc[k],mid+1,r,a,b,v);
		else update(lc[k],l,mid,a,mid,v),update(rc[k],mid+1,r,mid+1,b,v);
	}
	int gmax(int k,int l,int r,int x)
	{
		if(!k) return 0;
		if(l==r) return mx[k];
		int mid=l+r>>1;
		if(x<=mid) return max(mx[k],gmax(lc[k],l,mid,x));
		else return max(mx[k],gmax(rc[k],mid+1,r,x));
	}
}tr[N<<2];
void build(int k,int l,int r)
{
	tr[k].rt=tr[k].xd();
	if(l==r)
		return;
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
void update(int k,int l,int r,int a,int b,int a2,int b2,int v)
{
	if(l==a&&r==b)
	{
		tr[k].update(tr[k].rt,1,sy,a2,b2,v);
		return;
	}
	int mid=l+r>>1;
	if(b<=mid) update(k<<1,l,mid,a,b,a2,b2,v);
	else if(a>mid) update(k<<1|1,mid+1,r,a,b,a2,b2,v);
	else update(k<<1,l,mid,a,mid,a2,b2,v),update(k<<1|1,mid+1,r,mid+1,b,a2,b2,v);
}
int qmax(int k,int l,int r,int x,int y)
{
	if(l==r)
		return tr[k].gmax(tr[k].rt,1,sy,y);
	int mid=l+r>>1;
	if(x<=mid) return max(tr[k].gmax(tr[k].rt,1,sy,y),qmax(k<<1,l,mid,x,y));
	else return max(tr[k].gmax(tr[k].rt,1,sy,y),qmax(k<<1|1,mid+1,r,x,y));
}
void dfs(int u)
{
	vis[u]=1;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		dfs(v);
		if(s[u].size()<s[v].size())
			s[u].swap(s[v]);
		for(set<int>::iterator it=s[v].begin();it!=s[v].end();it++)
			s[u].insert(*it);
	}
	ans[a[u].id]=s[u].size();
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
		a[i].id=i;
		vx.push_back(a[i].x1),vx.push_back(a[i].x2);
		vy.push_back(a[i].y1),vy.push_back(a[i].y2);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&qx[i],&qy[i],&qt[i]);
		vx.push_back(qx[i]);
		vy.push_back(qy[i]);
	}
	sort(vx.begin(),vx.end());
	vx.erase(unique(vx.begin(),vx.end()),vx.end());
	sx=vx.size();
	sort(vy.begin(),vy.end());
	vy.erase(unique(vy.begin(),vy.end()),vy.end());
	sy=vy.size();
	for(int i=1;i<=n;i++)
	{
		a[i].x1=lower_bound(vx.begin(),vx.end(),a[i].x1)-vx.begin()+1;
		a[i].x2=lower_bound(vx.begin(),vx.end(),a[i].x2)-vx.begin()+1;
		a[i].y1=lower_bound(vy.begin(),vy.end(),a[i].y1)-vy.begin()+1;
		a[i].y2=lower_bound(vy.begin(),vy.end(),a[i].y2)-vy.begin()+1;
	}
	sort(a+1,a+n+1);
	build(1,1,sx);
	for(int i=1;i<=n;i++)
	{
		int f=qmax(1,1,sx,a[i].x1,a[i].y1);
		if(f)
			e[f].push_back(i);
		update(1,1,sx,a[i].x1,a[i].x2,a[i].y1,a[i].y2,i);
	}
	for(int i=1;i<=m;i++)
	{
		qx[i]=lower_bound(vx.begin(),vx.end(),qx[i])-vx.begin()+1;
		qy[i]=lower_bound(vy.begin(),vy.end(),qy[i])-vy.begin()+1;
		int f=qmax(1,1,sx,qx[i],qy[i]);
		if(f)
			s[f].insert(qt[i]);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])
			dfs(i);
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}

Compilation message (stderr)

plahte.cpp: In member function 'void seg::update(int&, int, int, int, int, int)':
plahte.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   int mid=l+r>>1;
      |           ~^~
plahte.cpp: In member function 'int seg::gmax(int, int, int, int)':
plahte.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int mid=l+r>>1;
      |           ~^~
plahte.cpp: In function 'void build(int, int, int)':
plahte.cpp:50:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |  int mid=l+r>>1;
      |          ~^~
plahte.cpp: In function 'void update(int, int, int, int, int, int, int, int)':
plahte.cpp:61:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int mid=l+r>>1;
      |          ~^~
plahte.cpp: In function 'int qmax(int, int, int, int, int)':
plahte.cpp:70:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int mid=l+r>>1;
      |          ~^~
plahte.cpp: In function 'void dfs(int)':
plahte.cpp:77:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i=0;i<e[u].size();i++)
      |              ~^~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
plahte.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |   scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |   scanf("%d%d%d",&qx[i],&qy[i],&qt[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32