Submission #1226069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226069		midi	Painting Walls (APIO20_paint)	C++20	28 / 100	1596 ms	14404 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 ll modit (ll x) { return ((x%m)+m)%m; }
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);
vcll dp(mxN,INF);

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.front().fi; }
	

} minq;

inline ll rmq (ll l, ll r)
{
	ll mn=INF, i;
	f0r(i,l,r) mina(mn,dp[i]);
	return mn;
}

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] ? rmq(i-m,i-1)+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]);
}

inline bool isin (ll x, vc<int> &a)
{
	// printf("a.sz(): %lli\n", (ll)a.sz());
	for (ll v:a) if (x==v) return 1;
	return 0;
}

inline bool colaei (ll i, ll r)
{
	// printf("kollaei to %lli, %lli?\n", i, r);
	ll j=i;
	f0r(i,j-m+1,j)
	{
		// printf("i: %lli, i-j+m: %lli\n", i, i-j+m);
		// printf("B[%lli].sz(): %lli\n", i-j+m, (ll)B[i-j+m-1].sz());
		if (!isin(ar[i],B[modit(i-j+m-1+r)])) return 0;
		// printf("saw if its in\n");
	}
	return 1;
}

inline bool bd_can_paint (ll i)
{
	// printf("trying to paint %lli\n", i);
	ll r;
	f0r(r,0,m-1) if (colaei(i,r)) return 1;
	return 0;
}

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("pre paint\n");
	f0r(i,m,n) can_paint[i]=bd_can_paint(i);
	// printf("after paint\n");
	// f0r(i,1,n) printf("can_paint[%lli]: %lli\n", i, (ll)can_paint[i]);
	do_dp();
	// printf("done\n");
	// printf("n: %lli, dp[n]: %lli\n", n, dp[n]);
	return dp[n]>=INF ? -1 : dp[n];
}

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