Submission #155472

#	Time	Username	Problem	Language	Result	Execution time	Memory
155472		TadijaSebez	Rope (JOI17_rope)	C++11	100 / 100	2303 ms	81876 KiB

rope

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1000050;
const int M=2*N;
struct SegmentTree
{
	int mx[M];
	SegmentTree(){}
	void Set(int i, int f){ mx[i+=N]+=f;for(i>>=1;i;i>>=1) mx[i]=max(mx[i<<1],mx[i<<1|1]);}
	int Get(int l, int r)
	{
		int ans=0;
		for(l+=N,r+=N;l<=r;l>>=1,r>>=1)
		{
			if(l%2==1) ans=max(ans,mx[l++]);
			if(r%2==0) ans=max(ans,mx[r--]);
		}
		return ans;
	}
} ST[2];
int a[N];
vector<int> pos[N];
int main()
{
	int n,k;
	scanf("%i %i",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%i",&a[i]);
		ST[0].Set(a[i],1);
		ST[1].Set(a[i],1);
		pos[a[i]].pb(i);
	}
	for(int i=1;i<=k;i++)
	{
		vector<int> del[2];
		for(int x:pos[i])
		{
			del[0].pb(x);
			del[1].pb(x);
			int y;
			if(x%2==1) y=x+1;
			else y=x-1;
			if(y>0 && y<=n && a[y]!=i) del[0].pb(y);
			if(x%2==0) y=x+1;
			else y=x-1;
			if(y>0 && y<=n && a[y]!=i) del[1].pb(y);
		}
		for(int x:del[0]) ST[0].Set(a[x],-1);
		for(int x:del[1]) ST[1].Set(a[x],-1);
		int ans=n-pos[i].size()-max(ST[0].Get(1,k),ST[1].Get(1,k));
		printf("%i\n",ans);
		for(int x:del[0]) ST[0].Set(a[x],1);
		for(int x:del[1]) ST[1].Set(a[x],1);
	}
	return 0;
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
rope.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&a[i]);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20