#include "paint.h"
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) x.begin(),x.end();
using ll=long long;
struct rmq{
vector<int> tree;
int sz;
rmq(int size){
sz=size;
tree.resize(size*2,0);
}
void add(int pos,int val){
pos+=sz;
tree[pos]+=val;
pos/=2;
while(pos>0){
tree[pos]=max(tree[pos*2],tree[pos*2+1]);
pos/=2;
}
}
int get_max(){
return tree[1];
}
};
int minimumInstructions(
int N, int M, int K, std::vector<int> C,
std::vector<int> A, std::vector<std::vector<int>> B) {
vector<vector<int>> cols(K);
rep(i,M){
for(int j:B[i]){
cols[j].emplace_back(i);
}
}
rmq seg(M);
vector<int> can(N,-1);
rep(i,N){
for(int j:cols[C[i]]){
seg.add((j-i+M)%M,1);
}
if(seg.get_max()==M){
can[i-M+1]=i-M+1;
}
if(i-M+1>=0){
for(int j:cols[C[i-M+1]]){
seg.add((j-(i-M+1)+M)%M,-1);
}
}
}
rep(i,N){
if(i!=0)can[i+1]=max(can[i],can[i+1]);
}
int pos=0;
int bef=-1;
int ans=0;
while(pos<N){
if(bef==can[pos])return -1;
bef=pos;
pos=can[pos]+M;
ans++;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
432 KB |
Output is correct |
3 |
Execution timed out |
1557 ms |
348 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
432 KB |
Output is correct |
3 |
Execution timed out |
1557 ms |
348 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
432 KB |
Output is correct |
3 |
Execution timed out |
1557 ms |
348 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
432 KB |
Output is correct |
3 |
Execution timed out |
1557 ms |
348 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
432 KB |
Output is correct |
3 |
Execution timed out |
1557 ms |
348 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |