Submission #51321

#	Time	Username	Problem	Language	Result	Execution time	Memory
51321		ho94949	Rope (JOI17_rope)	C++17	100 / 100	2495 ms	144580 KiB

rope

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1048576;
int idx[2*MAXN];
int getv(int a, int b)
{
	a += MAXN; b += MAXN;
	int ans = 0;
	while(a<=b)
	{
		if(a%2==1) ans = max(ans, idx[a++]);
		if(b%2==0) ans = max(ans, idx[b--]);
		a/=2; b/=2;
	}
	return ans;
}
void setv(int a, int v)
{
	idx[a+=MAXN] = v;
	while((a=a/2))
		idx[a] = max(idx[2*a], idx[2*a+1]);
}
void addv(int a, int v)
{
	idx[a+=MAXN] += v;
	while((a=a/2))
		idx[a] = max(idx[2*a], idx[2*a+1]);
}


int N, K;
vector<int> adj[MAXN];

int arr[MAXN];
int anseven[MAXN], ansodd[MAXN];
void even()
{
	for(int i=0; i<N/2; ++i)
	{
		int l = arr[2*i], r = arr[2*i+1];
		if(l == r)
			addv(l, 2);
		else
		{
			addv(l, 1); addv(r, 1);
			adj[l].push_back(r);
			adj[r].push_back(l);
		}
	}
	if(N%2==1) addv(arr[N-1], 1);
	for(int c=1; c<=K; ++c)
	{
		for(auto x: adj[c])
			addv(x, -1);
		
		anseven[c] = (getv(c, c) + max(getv(1, c-1), getv(c+1, K)));
		
		for(auto x: adj[c])
			addv(x, +1);
	}
}

void odd()
{
	addv(arr[0], 1);
	for(int i=0; i<(N-1)/2; ++i)
	{
		int l = arr[2*i+1], r = arr[2*i+2];
		if(l == r)
			addv(l, 2);
		else
		{
			addv(l, 1); addv(r, 1);
			adj[l].push_back(r);
			adj[r].push_back(l);
		}
	}
	if(N%2==0) addv(arr[N-1], 1);
	
	for(int c=1; c<=K; ++c)
	{
		for(auto x: adj[c])
			addv(x, -1);
		
		ansodd[c] = (getv(c, c) + max(getv(1, c-1), getv(c+1, K)));
		
		for(auto x: adj[c])
			addv(x, +1);
	}
	
}

int main()
{
	scanf("%d%d", &N, &K);
	for(int i=0; i<N; ++i) scanf("%d", arr+i);
	even();
	for(int i=1; i<=K; ++i) adj[i].clear();
	memset(idx, 0, sizeof idx);
	odd();
	for(int i=1; i<=K; ++i)
		printf("%d\n", N-max(anseven[i], ansodd[i]));
	return 0;
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
rope.cpp:96:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; ++i) scanf("%d", arr+i);
                         ~~~~~^~~~~~~~~~~~~

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