oj.uz

Submission #330797

# Submission time Handle Problem Language Result Execution time Memory
330797 2020-11-26T15:45:47 Z tzxydby Plahte (COCI17_plahte) C++11
160 / 160
 428 ms 69848 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=400005;
int n,m,sx,sy,tr[N<<2],f[N],ans[N];
vector<int>e[N],vx,vy;
set<int>s[N];
struct mat
{
	int x1,y1,x2,y2,id;
}a[N];
struct node
{
	int op,y1,y2,id;
	node(){}
	node(int _op,int _y1,int _y2,int _id):op(_op),y1(_y1),y2(_y2),id(_id){}
	bool operator<(const node &k)const
	{
		return op<k.op;
	}
};
vector<node>q[N];
void build(int k,int l,int r)
{
	if(l==r)
	{
		tr[k]=0;
		return;
	}
	tr[k]=-1;
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
void pushdown(int k)
{
	if(tr[k]!=-1)
	{
		tr[k<<1]=tr[k];
		tr[k<<1|1]=tr[k];
		tr[k]=-1;
	}
}
void update(int k,int l,int r,int a,int b,int v)
{
	if(l==a&&r==b)
	{
		tr[k]=v;
		return;
	}
	pushdown(k);
	int mid=l+r>>1;
	if(b<=mid) update(k<<1,l,mid,a,b,v);
	else if(a>mid) update(k<<1|1,mid+1,r,a,b,v);
	else update(k<<1,l,mid,a,mid,v),update(k<<1|1,mid+1,r,mid+1,b,v);
}
int query(int k,int l,int r,int x)
{
	if(l==r)
		return tr[k];
	pushdown(k);
	int mid=l+r>>1;
	if(x<=mid) return query(k<<1,l,mid,x);
	else return query(k<<1|1,mid+1,r,x);
}
void dfs(int u)
{
	for(auto v:e[u])
	{
		dfs(v);
		if(s[u].size()<s[v].size())
			s[u].swap(s[v]);
		for(auto i:s[v])
			s[u].insert(i);
	}
	ans[u]=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);
		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=n+1;i<=n+m;i++)
	{
		scanf("%d%d%d",&a[i].x1,&a[i].y1,&a[i].id);
		vx.push_back(a[i].x1);
		vy.push_back(a[i].y1);
	}
	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;
		q[a[i].x1].push_back(node(1,a[i].y1,a[i].y2,i));
		q[a[i].x2].push_back(node(3,a[i].y1,a[i].y2,i));	
	}
	for(int i=n+1;i<=n+m;i++)
	{
		a[i].x1=lower_bound(vx.begin(),vx.end(),a[i].x1)-vx.begin()+1;
		a[i].y1=lower_bound(vy.begin(),vy.end(),a[i].y1)-vy.begin()+1;
		q[a[i].x1].push_back(node(2,a[i].y1,a[i].y1,a[i].id));
	}
	build(1,1,sy);
	for(int i=1;i<=sx;i++)
	{
		sort(q[i].begin(),q[i].end());
		for(auto it:q[i])
		{
			int op=it.op,y1=it.y1,y2=it.y2,id=it.id;
			if(op==1)
			{
				int fa=query(1,1,sy,y1);
				f[id]=fa;
				e[fa].push_back(id);
				update(1,1,sy,y1,y2,id);
			}
			if(op==2)
			{
				int fa=query(1,1,sy,y1);
				s[fa].insert(id);
			}
			if(op==3)
			{
				update(1,1,sy,y1,y2,f[id]);
			}
		}
	}
	for(int i=1;i<=n;i++)
		if(!f[i])
			dfs(i);
	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}

Compilation message

plahte.cpp: In function 'void build(int, int, int)':
plahte.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |  int mid=l+r>>1;
      |          ~^~
plahte.cpp: In function 'void update(int, int, int, int, int, int)':
plahte.cpp:51:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int mid=l+r>>1;
      |          ~^~
plahte.cpp: In function 'int query(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 main()':
plahte.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
plahte.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |   scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |   scanf("%d%d%d",&a[i].x1,&a[i].y1,&a[i].id);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 47456 KB Output is correct
2 Correct 126 ms 48224 KB Output is correct
3 Correct 23 ms 37868 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 49632 KB Output is correct
2 Correct 147 ms 48736 KB Output is correct
3 Correct 23 ms 37996 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 59096 KB Output is correct
2 Correct 246 ms 54744 KB Output is correct
3 Correct 24 ms 37868 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 69848 KB Output is correct
2 Correct 414 ms 66008 KB Output is correct
3 Correct 23 ms 37868 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 67912 KB Output is correct
2 Correct 401 ms 65348 KB Output is correct
3 Correct 25 ms 37996 KB Output is correct