Submission #940793

#	Time	Username	Problem	Language	Result	Execution time	Memory
940793		sysia	Painting Walls (APIO20_paint)	C++17	100 / 100	251 ms	15992 KiB

paint

//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "paint.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef pair<int, int> T;
const int oo = 1e9+7, K = 30;

struct Tree{
	vector<int>tab;
	int size = 1;

	Tree(int n){
		while (size < n) size*=2;
		tab.assign(2*size, oo);
	}
	
	void update(int x, int v){
		x += size;
		tab[x] = v;
		while (x){
			x/=2;
			tab[x] = min(tab[2*x], tab[2*x+1]);
		}
	}

	int query(int l, int r){
		int ans = oo;
		for (l += size-1, r += size+1; r-l>1; l/=2, r/=2){
			if (!(l&1)) ans = min(ans, tab[l+1]);
			if (r&1) ans = min(ans, tab[r-1]);
		}
		return ans;
	}
};

int minimumInstructions(int n, int m, int k, vector<int>c, vector<int>len, vector<vector<int>>what){
	vector<vector<int>>who(k);
	for (int i = 0; i<m; i++){
		for (auto col: what[i]){
			who[col].emplace_back(i);
		}
	}
	for (int i = 0; i<k; i++){
		debug(i, who[i]);
	}
	vector<int>dp;
	vector<int>ok(n);
	for (int i = 0; i<n; i++){
		int s = (int)who[c[i]].size();
		vector<int>new_dp(s, 1);
		auto &t = who[c[i]];
		if (t.empty()) return -1;
		if (i){
			//przejscia jakies
			if (t[0] == 0 && who[c[i-1]].back() == m-1) new_dp[0] = max(new_dp[0], dp.back()+1);
			int ptr = -1;
			for (int j = 0; j<s; j++){
				while (ptr+1 < (int)who[c[i-1]].size() && who[c[i-1]][ptr+1] < t[j]) ptr++;
				if (ptr >= 0 && t[j]-who[c[i-1]][ptr] == 1) new_dp[j] = max(new_dp[j], dp[ptr]+1);
			}
		}
		dp.swap(new_dp);
		int mx = *max_element(dp.begin(), dp.end());
		if (mx >= m){
			ok[i] = 1;
		}
	}
	debug(ok);
	dp.assign(n, -1);
	if (!ok[m-1]) return -1;
	dp[m-1] = 1;
	Tree t(n+1);
	t.update(m-1, dp[m-1]);
	for (int i = m; i<n; i++){
		if (!ok[i]) continue;
		dp[i] = t.query(i-m, i-1)+1;
		t.update(i, dp[i]);
	}
	debug(dp);
	if (dp[n-1] < 0 || dp[n-1] > n) return -1;
	return dp[n-1];
}

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