Submission #965934

#	Time	Username	Problem	Language	Result	Execution time	Memory
965934		pcc	Painting Walls (APIO20_paint)	C++17	100 / 100	691 ms	17488 KiB

paint

#include "paint.h"

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

const int mxn = 1e5+10;
const int mxm = 2020;
#define pii pair<int,int>
#define fs first
#define sc second
vector<int> col[mxn];
bitset<mxn> able;
int N,M,K;
int arr[mxn];
int rp[mxn];
int dp[2][mxn];

namespace DP{
	void GO(){
		bool roll = false;
		for(int i = N-1;i>=0;i--){
			roll ^= 1;
			memset(dp[roll],0,sizeof(dp[roll]));
			for(auto &j:col[arr[i]]){
				int nx = j+1;
				if(nx>=M)nx -= M;
				dp[roll][j] = dp[roll^1][nx]+1;
				if(dp[roll][j]>=M)able[i] = true,rp[i] = i+M;
			}
		}
		return;
	}
}

namespace GETANS{
	struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
		int seg[mxn*4];
		void build(int now,int l,int r){
			if(l == r){
				seg[now] = rp[l];
				return;
			}
			build(ls,l,mid);
			build(rs,mid+1,r);
			seg[now] = max(seg[ls],seg[rs]);
		}
		int getval(int now,int l,int r,int s,int e){
			if(l>=s&&e>=r){
				return seg[now];
			}
			if(mid>=e)return getval(ls,l,mid,s,e);
			else if(mid<s)return getval(rs,mid+1,r,s,e);
			else return max(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
		}
#undef ls
#undef mid
#undef rs
	};
	SEG seg;

	int GO(){
		for(int i = 1;i<=N;i++)rp[i] = max(rp[i],rp[i-1]);
		int now = 0,ans = 0;
		while(ans<=N&&now<N){
			now = rp[now];
			ans++;
		}
		return (ans>N?-1:ans);
	}
}

int minimumInstructions(
    int NN, int MM, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
	N = NN,M = MM;
	for(int i = 0;i<M;i++){
		for(int j = 0;j<A[i];j++)col[B[i][j]].push_back(i);
	}
	for(int i = 0;i<N;i++)arr[i] = C[i];
	DP::GO();
	//for(int i = 0;i<N;i++)cerr<<able[i];cerr<<endl;
	return GETANS::GO();
}

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