| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 745380 | Lobo | 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"
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
const int maxn = 2e5+10;
const int inf = 1e9+10;
int minimumInstructions(int n, int m, int k, vector<int> c,vector<int> a, vector<vector<int>> b) {
vector<int> f[k];
for(int i = 0; i < m; i++) {
sort(all(b[i]));
for(auto x : b[i]) {
f[x].pb(i);
}
}
vector<pair<int,int>> pos;
for(int i = n-1; i >= 0; i-= max(1LL,m/2)) {
for(auto j : f[c[i]]) {
int cnt;
int li = i;
int lj = j;
cnt = 0;
while(cnt++ <= m) {
if(li < 0 || b[lj].back() < c[li] || *lower_bound(all(b[lj]),c[li]) != c[li]) {
li++;
break;
}
li--;
lj--;
lj = (lj%m+m)%m;
}
int ri = i;
int rj = j;
cnt = 0;
while(cnt++ <= m) {
if(ri > n-1 || b[rj].back() < c[ri] || *lower_bound(all(b[rj]),c[ri]) != c[ri]) {
ri--;
break;
}
ri++;
rj++;
rj = (rj%m+m)%m;
}
pos.pb(mp(li,ri));
// cout << i << " " << j << " " << li << " " << ri << endl;
}
}
sort(all(pos));
vector<pair<int,int>> pos1;
for(auto X : pos) {
while(pos1.size() && pos1.back().fr == X.fr) pos1.pop_back();
if(pos1.size() && pos1.back().sc >= X.sc) continue;
pos1.pb(X);
}
swap(pos,pos1);
reverse(all(pos));
for(auto x : pos) {
// cout << x.fr << " " << x.sc << endl;
}
vector<int> dp(n+1,inf);
dp[0] = 0;
priority_queue<pair<int,int>> pq;
pq.push(mp(0,0));
pq.push(mp(-inf,n));
for(int i = 0; i <= n; i++) {
while(pq.top().sc < i) pq.pop();
dp[i] = -pq.top().fr;
if(dp[i] == inf) continue;
while(pos.size() && pos.back().sc < i+m-1) pos.pop_back();
if(pos.empty() || pos.back().fr > i) continue;
pq.push(mp(-(dp[i]+1),i+m));
}
if(dp[n] == inf) return -1;
return dp[n];
}