Submission #1226072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226072		midi	Painting Walls (APIO20_paint)	C++20	63 / 100	659 ms	589824 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll,ll> prll;

#define fi first
#define se second
#define sz size
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(x) ((x).begin()), ((x).end())

#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)

inline void maxa (ll &a, ll b) { if (a<b) a=b; }
inline void mina (ll &a, ll b) { if (a>b) a=b; }


#define mxN (100'010ll)
#define mxM (50'010ll)
#define mxK (100'010ll)
#define INF (LLONG_MAX>>3ll)

ll n, m, k;
vcll ar(mxN);
vc<vc<int>> B;

vc<vcll> cl_needs(mxN);
vc<vcll> pl_needs(mxN);
vcll temp_fr(mxK,0);

inline void clean_dups (vcll &a)
{
	for (ll c:a) temp_fr[c]=1;
	vcll b;
	for (ll c:a) if (temp_fr[c])
	{
		b.pb(c);
		temp_fr[c]=0;
	}
}

inline ll modit (ll x) { return ((x%m)+m)%m; }
inline void bd_needs()
{
	ll i, j;
	f0r(j,0,m-1) for (int c:B[j]) cl_needs[c].pb(j+1);
			// // printf("%lli needs %lli\n", (ll)c, j+1);


	f0r(i,1,n)
	{
		for ( ll J:cl_needs[ar[i]])
		{
			pl_needs[i].pb(modit(J-i));
			// printf("pl %lli, needs %lli\n", i, modit(J-i));
		}
		clean_dups(pl_needs[i]);
	}
}

vcll fr(mxK,0);
ll good_cnt;

inline void push (ll i)
{
	for (ll r:pl_needs[i])
		if (++fr[r]==m) good_cnt++;
}

inline void pull (ll i)
{
	for (ll r:pl_needs[i])
		if (fr[r]--==m) good_cnt--;
}

vcb can_paint(mxN,0);
vcll dp(mxN,INF);

inline void slide()
{
	ll i, j;
	good_cnt=0;
	f0r(i,1,m) push(i);
	can_paint[m]=good_cnt;
	f0r(i,m+1,n)
	{
		push(i);
		pull(i-m);
		can_paint[i]=good_cnt;
	}
	// f0r(i,1,n) printf("can_paint[%lli]: %lli\n", i, (ll)can_paint[i]);
}

struct MINQ
{
	ll push_time, pop_time;
	deque<prll> q;

	inline MINQ()
	{
		push_time=0;
		pop_time=0;
		while (q.sz()) q.ppb();
		q.pb({INF,0});
	}

	inline void push (ll x)
	{
		while (q.sz() and x<q.back().fi) q.ppb();
		q.pb({x,++push_time});
		// printf("pushed {%lli, %lli}\n", x, push_time);
	}
	inline void pop () { if (q.sz() and q.front().se == ++pop_time)
		{
			// printf("popping {%lli, %lli}\n", q.front().fi, q.front().se);
			q.ppf();
		}
	}
	inline ll min() { return q.sz() ? q.front().fi : INF; }
	

} minq;

inline void do_dp()
{
	dp[0]=0;
	ll i;
	f0r(i,0,m-1) minq.push(dp[i]);
	// printf("dp[1]: %lli\n", dp[1]);

	f0r(i,m,n)
	{
		/*
		printf("i: %lli\n", i);
		if (can_paint[i])
		{
			printf("%lli is good, minq.min(): %lli\n", i, minq.min());
		}
		*/
		dp[i] = can_paint[i] ? minq.min()+1 : INF;
		minq.push(dp[i]);
		// printf("pushinggggggggggggggg\n");
		minq.pop();
		// printf("poppinnnnnnnnnnnnnnn\n");
	}
	// f0r(i,1,n) printf("dp[%lli]: %lli\n", i, dp[i]);
}

int minimumInstructions( int N, int M, int K, vc<int> C, vc<int> A, vc<vc<int>> bar)
{
	n=N; m=M; k=K;
	swap(B,bar);
	ll i, j;
	f0r(i,1,n) ar[i]=C[i-1];
	// printf("got input\n");
	bd_needs();
	// printf("bt needs\n");
	slide();
	// printf("slided\n");
	do_dp();
	// printf("done\n");
	// printf("n: %lli, dp[n]: %lli\n", n, dp[n]);
	return dp[n]>=n+10 ? -1 : dp[n];
}

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 0 / 37