#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];
PIII 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){
set<int>::iterator it,it1,it2,sol,sag;
//printf("gir%lld %lld %lld %lld %lld\n",l,r,u,i,ekle );
if(u==dizi[i].f1){dpf(l,r,u+1,i,ekle);return;}
if(dp[l][r][u]==0)return;
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(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++;
sag=s[dizi[i].f1].upper_bound(i);
if(sag!=s[dizi[i].f1].end() && *sag<*it2 )return;
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);
// else
// printf("sicis %lld\n",tot);
}
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);
}
else{
//printf("sag%lld %lld %lld %lld %lld %lld\n",l,r,u,i,ekle,*it );
dpf(l,r,u+1,i,ekle);
}
}
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);
}
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);
}
}
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);
}
// printf("%lld\n", dizi[970].f1);
int mx=0;
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);
}
}
}
for(int i=0;i<=n;i++){
s[0].insert(i);
}
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);
// //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);
// 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:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
98 | scanf("%lld %lld %lld",&n,&k,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
100 | scanf("%lld",&dizi[i].f1);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
135 | scanf("%lld",&a);
| ~~~~~^~~~~~~~~~~
nekameleoni.cpp:145:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
145 | scanf("%lld %lld",&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
377 ms |
2028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1327 ms |
2284 KB |
Output is correct |
| 2 |
Correct |
369 ms |
2284 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3057 ms |
2452 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3065 ms |
4460 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3064 ms |
8428 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3022 ms |
7020 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3033 ms |
9836 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3082 ms |
9196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3073 ms |
14060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3055 ms |
14060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
