| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 949712 | smartmonky | Painting Walls (APIO20_paint) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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
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];
}