제출 #546031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546031		amunduzbaev	벽 칠하기 (APIO20_paint)	C++17	40 / 100	1594 ms	413832 KiB

paint

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

#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array

const int MAXN = 1e5 + 5;
struct ST{
	int tree[MAXN << 2];
	ST(){
		memset(tree, 63, sizeof tree);
	}
	
	void sett(int i, int v, int lx = 0, int rx = MAXN, int x = 1){
		if(lx == rx) { tree[x] = v; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = MAXN, int x = 1){
		if(lx > r || rx < l) return 1e9;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return min(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}tree;

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b){
	vector<vector<int>> rev(k + 1);
	for(int i=0;i<m;i++){
		for(int j=0;j<a[i];j++){
			rev[b[i][j]].push_back(i);
		}
	}
	
	vector<vector<int>> dp(n + 1);
	vector<map<int, int>> T(n + 1);
	vector<int> is(n + 1);
	for(int i=0;i<n;i++){
		int l = 0, sz = rev[c[i]].size(), ps = (i ? rev[c[i-1]].size() : 0);
		dp[i+1].resize(sz, 1);
		for(int j=0;j<sz;j++){
			while(l<ps && rev[c[i-1]][l] < rev[c[i]][j] - 1) l++;
			if(l<ps && rev[c[i-1]][l] == rev[c[i]][j] - 1){
				dp[i+1][j] += dp[i][l];
			}
		}
		if(ps && sz && !rev[c[i]][0] && rev[c[i-1]].back() == m - 1){
			dp[i+1][0] += dp[i].back();
		}
		
		for(auto j : rev[c[i]]){
			if(T[i].count((j + m - 1) % m)){
				T[i+1][j] = T[i][(j + m - 1) % m] + 1;
			} else {
				T[i+1][j] = 1;
			}
		}
		
		assert(T[i+1].size() == dp[i+1].size());
		for(int j=0;j<sz;j++){
			assert(T[i+1][rev[c[i]][j]] == dp[i+1][j]);
		}
		for(auto x : dp[i+1]) is[i+1] |= (x >= m);
	}
	
	vector<int> tp(n + 1, 1e9);
	tree.sett(0, 0);
	for(int i=1;i<=n;i++){
		if(is[i]){
			tp[i] = min(tp[i], tree.get(i - m, i - 1) + 1);
			tree.sett(i, tp[i]);
		}
	}
	
	//~ for(int i=1;i<=n;i++) cout<<tree.get(i, i)<<" ";
	//~ cout<<"\n";
	//~ for(int i=1;i<=n;i++) cout<<is[i]<<" ";
	//~ cout<<"\n";
	//~ for(int i=1;i<=n;i++) cout<<tp[i]<<" ";
	//~ cout<<"\n";
	
	if(tp[n] == 1e9) return -1;
	else return tp[n];
}

/*

8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4

5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3

*/

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