Submission #1136466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136466		wilbur	Plahte (COCI17_plahte)	C++20	0 / 160	145 ms	38244 KiB

plahte

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+50;
int n,m,cnt,Cnt;
int fa[N],head[N],ans[N],belong[N];
struct edge{
	int to,nxt;
}e[N*2];
void add(int u,int v)
{
	e[++Cnt].to=v;
	e[Cnt].nxt=head[u];
	head[u]=Cnt;
}
struct node{
	int l,r,x,op,id;
	bool operator <(const node &a)const{
		if(x!=a.x)return x<a.x;
		return op<a.op;
	}
}p[N*2],q[N];
struct line{
	int l,op,id;
	bool operator <(const line &a)const{
		if(l!=a.l)return l<a.l;
		return op<a.op;
	}
};
set<line> s;
set<int> res[N];
void dfs(int u)
{
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		dfs(v);
		if(res[belong[u]].size()>res[belong[v]].size())
		{
			for(auto j:res[belong[v]])res[belong[u]].insert(j);
			res[belong[v]].clear();
		}
		else
		{
			for(auto j:res[belong[u]])res[belong[v]].insert(j);
			res[belong[u]].clear();
			belong[u]=belong[v];
		}
	}
	ans[u]=res[belong[u]].size();
}
signed main()
{
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int a,b,c,d;belong[i]=i;
		scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
		p[++cnt]=node{b,d,a,1,i};p[++cnt]=node{b,d,c+1,2,i};
	}
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		q[i]=node{b,b,a,c,i};
	}
	sort(p+1,p+1+cnt);sort(q+1,q+1+m);
	int j=1;
	for(int i=1;i<=m;i++)
	{
		while(j<=cnt&&p[j].x<=q[i].x)
		{
			if(p[j].op==1)
			{
				auto it=s.upper_bound(line{p[j].r,0,p[j].id});
				if(it!=s.end())
				{
					if((*it).op==1)fa[p[j].id]=(*it).id;
					else fa[p[j].id]=fa[(*it).id];
				}
				s.insert(line{p[j].r,1,p[j].id});s.insert(line{p[j].l,2,p[j].id});
			}
			else{s.erase(line{p[j].r,1,p[j].id});s.erase(line{p[j].l,2,p[j].id});}
			j++;
		}
		auto it=s.lower_bound(line{q[i].r,0,0});
		if(it==s.end())continue;
		if((*it).op==2)continue;
		res[(*it).id].insert(q[i].op);
	}
	for(int i=1;i<=n;i++)add(fa[i],i);
	dfs(0);
	for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
	return 0;
}
/*
4 3
1 1 7 7
2 2 6 6
3 3 5 5
4 4 4 4
2 6 2
4 7 3
4 4 1
*/

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%lld %lld",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
plahte.cpp:58:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |                 scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:64:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |                 scanf("%lld %lld %lld",&a,&b,&c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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