#include<bits/stdc++.h>
#define int long long
#define N 100005
#define pb push_back
#define f1 first
#define s2 second
#define PII pair<int,int>
#define PIII pair<int,PII>
using namespace std;
int n,k,m,ans;
int dp[55][55][55];
PII dizi[N];
set<int>s[100];
set<int>::iterator it,it1,it2;
multiset<int>anss;
multiset<int>::iterator mit;
void dpf(int l,int r,int u,int i,int ekle,bool shet){
set<int>::iterator it,it1,it2,sol,sag;
if(u==dizi[i].f1){dpf(l,r,u+1,i,ekle,shet);return;}
if(dp[l][r][u]==0)return;
// printf("gir%lld %lld %lld %lld %lld\n",l,r,u,i,ekle );
if(u==k+1){
dp[l][r][u]=0;
it1=s[l].upper_bound(i);
it1--;
// //printf("%lld\n", *it1);
it2=s[r].lower_bound(i);
it=it2;
if(1){
if(r!=0 && l!=0 && it2!=s[r].begin() && (*(--it2)>*it1))return;
it2=it;
if( (++it1)!=s[l].end()&& l!=0 && r!=0 && (*(it1)<*it2))return;
it1--;}
int tot;
tot=i-(*(it1));
tot+=(*(it2))-i;
tot++;
if(l==0){
sag=s[dizi[i].f1].upper_bound(i);
if(sag!=s[dizi[i].f1].end() && *sag<*it2 )return;
}
if(r==0){
sol=s[dizi[i].f1].lower_bound(i);
if(sol!=s[dizi[i].f1].begin() &&*(--sol)>*it1 )return;
}
// //printf("%lld %lld %lld\n",i-(*(it1)),(*(it2))-i,tot );
// printf("sil %lld %lld %lld %lld %lld %lld\n",l,r,u,i,ekle,tot );
// if(tot==19)printf("aaaa%lld %lld\n",ekle,ans );
if(ekle)
anss.insert(tot);
else{
it=anss.find(tot);
if(it!=anss.end())
anss.erase(it);
// elsed
}
return;
}
dp[l][r][u]=0;
it=s[u].lower_bound(i);
//printf("it:%lld\n",*it );
if(it!=s[u].end()){
if(*it>=*s[r].lower_bound(i)){
//printf("sa %lld %lld %lld %lld %lld %lld\n",l,u,u,i,ekle,*it );
dpf(l,u,u+1,i,ekle,shet);
}
else{
//printf("sag%lld %lld %lld %lld %lld %lld\n",l,r,u,i,ekle,*it );
dpf(l,r,u+1,i,ekle,shet);
}
}
if(it!=s[u].begin()){
//printf("%lld %lld\n",*s[u].begin(),*it );
it--;
it1=s[l].upper_bound(i);
it1--;
if(*it<=*it1){
//printf("so %lld %lld %lld %lld %lld %lld %lld\n",u,r,u,i,ekle,*it,*it1 );
dpf(u,r,u+1,i,ekle,shet);
}
else{
//printf("sol%lld %lld %lld %lld %lld %lld %lld\n",l,r,u,i,ekle,*it,*it1 );
dpf(l,r,u+1,i,ekle,shet);
}
}
return;
}
int32_t main(){
// freopen("a.gir","r",stdin);
// freopen("a.cik","w",stdout);
scanf("%lld %lld %lld",&n,&k,&m);
for(int i=0;i<n;i++){
scanf("%lld",&dizi[i].f1);
s[dizi[i].f1].insert(i);
dizi[i].s2=1;
}
// printf("%lld\n", dizi[970].f1);
int mx=0;
for(int i=0;i<=n;i++){
s[0].insert(i);
}
for(int i=0;i<n;i++){
mx=0;
for(int j=1;j<=k;j++){
if(j==dizi[i].f1)continue;
it=s[j].lower_bound(i);
if(it==s[j].end()){
mx=-1;
break;
}
mx=max(mx,*it-i+1);
}
if(mx!=-1){
it=s[dizi[i].f1].upper_bound(i);
if(it==s[dizi[i].f1].end() || *it-i+1>mx){
// printf("%lld\n", i);
anss.insert(mx);
}
}
}
anss.insert(INT_MAX);
int a,b,c;
for(int i=0;i<m;i++){
// for(mit=anss.begin();mit!=anss.end();mit++){
// printf("%lld ",*mit );
// }
// printf("\n");
ans=i;
scanf("%lld",&a);
if(a==2){
// //printf("%lu ",anss.size() );
printf("%lld\n",*(anss.begin())==INT_MAX?-1:*(anss.begin()) );
}
else{
// for(mit=anss.begin();mit!=anss.end();mit++){
// printf("%lld ",*mit );
// }
// printf("\n");
scanf("%lld %lld",&b,&c);
b--;
memset(dp,-1,sizeof(dp));
dpf(0,0,1,b,0,dizi[i].s2);
dizi[i].s2=0;
// //printf("~~%lld\n",dizi[b].f1);
s[dizi[b].f1].erase(b);
dizi[b].f1=c;
s[c].insert(b);
// // //printf("~~%lld\n",dizi[b].f1);
memset(dp,-1,sizeof(dp));
// for(mit=anss.begin();mit!=anss.end();mit++){
// printf("%lld ",*mit );
// }
// printf("\n");
dpf(0,0,1,b,1,dizi[i].s2);
// for(mit=anss.begin();mit!=anss.end();mit++){
// printf("%lld ",*mit );
// }
// printf("\n\n");
//printf("---------bitti\n");
// printf("\n");
// for(it=s[1].begin();it!=s[1].end();it++){
// printf("%lld ",*it );
// }
// printf("\n\n");
}
}
}
Compilation message
nekameleoni.cpp: In function 'int32_t main()':
nekameleoni.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
102 | scanf("%lld %lld %lld",&n,&k,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
104 | scanf("%lld",&dizi[i].f1);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
140 | scanf("%lld",&a);
| ~~~~~^~~~~~~~~~~
nekameleoni.cpp:150:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
150 | scanf("%lld %lld",&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
352 ms |
2228 KB |
Output is correct |
| 2 |
Correct |
251 ms |
2028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1312 ms |
2204 KB |
Output is correct |
| 2 |
Correct |
341 ms |
2284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3080 ms |
2540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3048 ms |
4204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3058 ms |
8044 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3035 ms |
6508 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3075 ms |
9196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3076 ms |
8684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3032 ms |
13292 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3049 ms |
13376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
