Submission #1097669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097669		vjudge1	Inside information (BOI21_servers)	C++14	100 / 100	209 ms	55384 KiB

servers

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=310000;
int n,m,s,l,a1[N],a2[N],rt[N],ans[N];
char op[N];
struct point
{
	int sum,lp,rp;
};
struct dgb_segment_tree
{
	int n=0;
	point a[(N<<2)*100];
	int newp()
	{
		++n;
		a[n].sum=a[n].lp=a[n].rp=0;
		return n;
	}
	void pushup(int p)
	{
		a[p].sum=0;
		if(a[p].lp)
			a[p].sum+=a[a[p].lp].sum;
		if(a[p].rp)
			a[p].sum+=a[a[p].rp].sum;
//		a[p].sum=a[a[p].lp].sum+a[a[p].rp].sum;
	}
	void change(int oldroot,int &p,int l,int r,int x,int d)
	{
		p=newp();
		a[p]=a[oldroot];
		if(l==r)
		{
			a[p].sum+=d;
//			cout<<p<<" "<<l<<" "<<r<<" "<<a[p].sum<<endl;
			return ;
		}
		int mid=(l+r)>>1;
//		cout<<"P"<<p<<endl;
		if(x<=mid)
			change(a[oldroot].lp,a[p].lp,l,mid,x,d);
		else
			change(a[oldroot].rp,a[p].rp,mid+1,r,x,d);
		pushup(p);
//		cout<<p<<" "<<l<<" "<<r<<" "<<a[p].sum<<endl;
	}
	inline int merge(int x,int y,int l,int r)
	{
		if(!x||!y)
			return x|y;
		int p=newp();
		if(l==r)
		{
			a[p].sum=a[x].sum+a[y].sum;
			return p;
		}
		int mid=(l+r)>>1;
		a[p].lp=merge(a[x].lp,a[y].lp,l,mid);
		a[p].rp=merge(a[x].rp,a[y].rp,mid+1,r);
		pushup(p);
		return p;
	}
	int ask(int p,int l,int r,int askl,int askr)
	{
//		cout<<p<<" "<<l<<" "<<r<<" "<<a[p].sum<<endl;
		if(!p)
			return 0; 
		if(askl<=l&&r<=askr)
			return a[p].sum;
		int mid=(l+r)>>1,sum=0;
		if(askl<=mid)
			sum+=ask(a[p].lp,l,mid,askl,askr);
		if(mid<askr)
			sum+=ask(a[p].rp,mid+1,r,askl,askr);
		return sum;
	}
	void clear()
	{
		for(int i=0;i<=n;i++)
			a[i].lp=a[i].rp=a[i].sum=0;
		n=0;
	}
}T;
int main()
{
	scanf("%d%d",&n,&m);
	m+=n-1;
	rt[0]=T.newp();
//	cout<<T.a[rt[0]].sum<<endl;
	for(int i=1;i<=n;i++)
	{
		T.change(rt[0],rt[i],1,n,i,1);
//		cout<<T.a[rt[i]].sum<<endl;
	}
	for(int i=1;i<=m;i++)
	{
		do
		{
			op[i]=getchar();
		}while(op[i]!='S'&&op[i]!='Q'&&op[i]!='C');
		if(op[i]=='S')
		{
			scanf("%d%d",&a1[i],&a2[i]);
			rt[a1[i]]=rt[a2[i]]=T.merge(rt[a1[i]],rt[a2[i]],1,n);
		}
		if(op[i]=='Q')
		{
			scanf("%d%d",&a1[i],&a2[i]);
			ans[i]=T.ask(rt[a1[i]],1,n,a2[i],a2[i]);
		}
		if(op[i]=='C')
			scanf("%d",&a1[i]);
	}
	T.clear();
	for(int i=1;i<=n;i++)
	{
		rt[i]=T.newp();
	}
	for(int i=m;i>=1;i--)
		if(op[i]=='S')
		{
			T.change(rt[a1[i]],rt[a1[i]],1,m,i,1);
			rt[a1[i]]=rt[a2[i]]=T.merge(rt[a1[i]],rt[a2[i]],1,m);
		}
	for(int i=1;i<=m;i++)
	{
		if(op[i]=='Q')
		{
			if(ans[i])
				puts("yes");
			else
				puts("no");
		}
		if(op[i]=='C')
		{
			printf("%d\n",T.ask(rt[a1[i]],1,m,1,i)+1);
		}
	}
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
servers.cpp:106:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |    scanf("%d%d",&a1[i],&a2[i]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:111:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |    scanf("%d%d",&a1[i],&a2[i]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:115:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |    scanf("%d",&a1[i]);
      |    ~~~~~^~~~~~~~~~~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5