#include "paint.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib>
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
//#define int long long
/*
sum of f(k)^2 is 4e5
max f(k)is 633????
we can do nf(k)
*/
const int mxn=2e5,mod=1e9+7,inf=1e9;
vector<pii>go[mxn+10];//for each col
int ans[mxn+10],mn[mxn+10];//ans=endpoint of using i
int32_t minimumInstructions(int32_t n, int32_t m, int32_t k,vector<int32_t>c,vector<int32_t> A,vector<vector<int32_t>>B){
for(int i=0;i<m;i++)for(auto j:B[i])go[j].pb({i,0});
int cur=0;
auto get=[&](int x){
int l=0,r=cur,pos=inf;
while(l<=r){
int mid=l+(r-l)/2;
if(x<=ans[mid])r=mid-1,pos=min(pos,mid);
else l=mid+1;
}
return pos;
};
for(int i=0;i<=k;i++)mn[i]=inf;
for(int i=0;i<n;i++){
for(auto &j:go[c[i]]){
if(mn[j.f]!=inf)j.s=mn[j.f];
else j.s=i;//start here
if(i-j.s+1>=m&&i-m+1>=0){
int x=get(i-m);
if(x==inf)continue;
ans[x+1]=max(ans[x+1],i);
cur=x+1;
}
}
if(i)for(auto j:go[c[i-1]])mn[(j.f+1)%m]=inf;//clear
for(auto j:go[c[i]])mn[(j.f+1)%m]=min(mn[(j.f+1)%m],j.s);//nxt start
}
if(ans[cur]<n-1)return -1;
return cur;
}
/*
int32_t main(){
int n,m,k;cin>>n>>m>>k;
vector<int>c(n),a(m);
vector<vector<int>>b(m);
for(int i=0;i<n;i++)cin>>c[i];
for(int i=0;i<m;i++){
cin>>a[i];
for(int j=0;j<a[i];j++){
int x;cin>>x;
b[i].pb(x);
}
}
cout<<minimumInstructions(n,m,k,c,a,b);
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
