#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-= m) {
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;
// cout << i << " " << dp[i] << " " << i+m << endl;
pq.push(mp(-(dp[i]+1),i+m));
// dp[i+m] = dp[i]+1;
// for(int j = i+1; j <= i+m; j++) {
// dp[j] = min(dp[j],dp[i]+1);
// }
}
if(dp[n] == inf) return -1;
return dp[n];
}
Compilation message
paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:65:14: warning: variable 'x' set but not used [-Wunused-but-set-variable]
65 | for(auto x : pos) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
