| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 395240 | 2021-04-28T03:47:41 Z | abc864197532 | Painting Walls (APIO20_paint) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
// #include "grader_paint.cpp"
using namespace std;
#define int int_fast32_t
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
for (auto i : x) cout << i << ' ';\
cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
return o >> a.X >> a.Y;
}
int minimumInstructions(int n, int m, int k,vector <int> c, vector <int> a, vector <vector <int>> b) {
vector <int> tmp[n], pos[k];
int cha[n];
for (int i = 0; i < n; ++i) cha[i] = i < m ? i : cha[i - m];
for (int i = 0; i < n; ++i) pos[c[i]].pb(i);
for (int i = 0; i < m; ++i) {
for (int j : b[i]) {
for (int ii : pos[j]) {
int t = ii - i;
t = t >= 0 ? cha[t] : t + m;
tmp[ii].pb(t);
}
}
}
int cnt[m]{}, num[m + 1]{}, dp[n + 1]{};
num[0] = m;
for (int i = 0; i < n + 1; ++i) dp[i] = -1;
dp[0] = 0;
for (int i = 0; i < m; ++i) {
for (int j : tmp[i]) {
num[cnt[j]]--;
cnt[j]++;
num[cnt[j]]++;
}
}
deque <int> dq;
if (num[m] > 0) dp[m] = 1, dq.push_back(m);
for (int i = m; i < n; ++i) {
for (int j : tmp[i - m]) {
num[cnt[j]]--;
cnt[j]--;
num[cnt[j]]++;
}
for (int j : tmp[i]) {
num[cnt[j]]--;
cnt[j]++;
num[cnt[j]]++;
}
if (num[m] > 0) {
while (!dq.empty() && dq.front() <= i - m) dq.pop_front();
if (!dq.empty()) dp[i + 1] = dp[dq.front()] + 1;
if (dp[i + 1] != -1) {
while (!dq.empty() && dp[dq.back()] >= dp[i + 1]) dq.pop_back();
dq.push_back(i + 1);
}
}
}
return dp[n];
}