| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 605260 | inksamurai | Nekameleoni (COCI15_nekameleoni) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3Pxrs5V ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
//e
const int inf=200011;
const int _n=340002;
const int _k=51;
struct node{
int res;
int l[_k],r[_k];
};
node seg[_n];
int k; // initial k
void update_node(int &node,int &val,int &t=0){
if(val==-1){
return;
}
if(node==-1){
node=val;
}else{
if(t==0){
node=min(node,val);
}else{
node=max(node,val);
}
}
}
vec(pii) evs;
void update(int node,int l,int r,int pos,int v){
if(l==r-1){
rep(i,k){
seg[node].l[i]=-1;
seg[node].r[i]=-1;
}
seg[node].l[v]=seg[node].r[v]=l;
seg[node].res=inf;
return;
}
int m=(l+r)>>1;
if(pos<m){
update(node*2,l,m,pos,v);
}else{
update(node*2+1,m,r,pos,v);
}
seg[node].res=inf;
seg[node].res=min(seg[node*2].res,seg[node*2+1].res);
evs.clear();
rep(i,k){
int l=seg[node*2].r[i];
int r=seg[node*2+1].l[i];
l=(l!=-1?l:-inf);
r=(r!=-1?r:inf);
// if(node==1){
// print(l,r);
// }
evs.emplace_back(r,l);
int v0l=seg[node*2].l[i];
int v0r=seg[node*2].r[i];
int v1l=seg[node*2+1].l[i];
int v1r=seg[node*2+1].r[i];
seg[node].l[i]=seg[node].r[i]=-1;
update_node(seg[node].l[i],v0l);
update_node(seg[node].l[i],v0r);
update_node(seg[node].l[i],v1l);
update_node(seg[node].l[i],v1r);
update_node(seg[node].r[i],v0l,1);
update_node(seg[node].r[i],v0r,1);
update_node(seg[node].r[i],v1l,1);
update_node(seg[node].r[i],v1r,1);
}
// print("\n.....");
sort(evs.begin(), evs.end());
int mi=inf;
per(i,sz(evs)){
if(mi==-inf){
break;
}
if(evs[i].fi!=inf and mi!=inf){
seg[node].res=min(seg[node].res,evs[i].fi-mi+1);
}
mi=min(mi,evs[i].se);
}
}
signed main(){
_3Pxrs5V;
int n,q;
cin>>n>>k>>q;
rep(i,n){
int v;
cin>>v;
v-=1;
update(1,0,n,i,v);
}
rep(_,q){
int t;
cin>>t;
if(t==1){
int i,v;
cin>>i>>v;
i-=1,v-=1;
// print(i,v);
update(1,0,n,i,v);
}else{
if(k==1){
cout<<"1\n";
}else{
int res=seg[1].res;
cout<<(res>n?-1:res)<<"\n";
// cout<<seg[1].res<<"\n";/
}
}
}
}