#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#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=200000;
const int _n=3400; // fix me
int a[_n];
struct node{
int res=inf;
vector<pair<ll,int>> l;
vector<pair<ll,int>> r;
};
struct tournament{
int n,k;
int id[_n]; // node id for position
node seg[_n];
tournament(int _n=0,int _k=0){
n=_n;
k=_k;
build(1,0,n);
}
void merge(int node){
seg[node].l=seg[node*2].l;
seg[node].r=seg[node*2+1].r;
seg[node].res=inf;
seg[node].res=min(seg[node*2].res,seg[node*2+1].res);
rep(i,sz(seg[node*2+1].l)){
pair<ll,int> v=seg[node*2+1].l[i];
if(sz(seg[node].l)){
pair<ll,int> p=seg[node].l.back();
if(!((p.fi&v.fi)==v.fi)){
seg[node].l.pb({p.fi|v.fi,v.se});
}
}else{
seg[node].l.pb(v);
}
}
rep(i,sz(seg[node*2].r)){
pair<ll,int> v=seg[node*2].r[i];
if(sz(seg[node].r)){
pair<ll,int> p=seg[node].r.back();
if(!((p.fi&v.fi)==v.fi)){
seg[node].r.pb({p.fi|v.fi,v.se});
}
}else{
seg[node].r.pb(v);
}
}
if(sz(seg[node].l)==k){
seg[node].res=min(seg[node].res,seg[node].l.back().se-seg[node].l[0].se+1);
}
if(sz(seg[node].r)==k){
seg[node].res=min(seg[node].res,seg[node].r[0].se-seg[node].r.back().se+1);
}
int posl=0;
const ll need=(1ll<<k)-1;
per(i,sz(seg[node*2+1].l)){
ll now=seg[node*2+1].l[i].fi;
int posr=seg[node*2+1].l[i].se;
while(posl<sz(seg[node*2].r) and (now|seg[node*2].r[posl].fi)!=need){
posl+=1;
}
// if(node==1){
// print("hooo",now|seg[node*2].r[posl].fi,need);
// }
if(posl<sz(seg[node*2].r) and (now|seg[node*2].r[posl].fi)==need){
// if(node==1){
// print(posr,seg[node*2].r[posl].se);
// }
// print("ooo");
seg[node].res=min(seg[node].res,posr-seg[node*2].r[posl].se+1);
}
}
// if(node==1){
// for(auto p:seg[node*2+1].l){
// print(p.fi,p.se);
// }
// }
}
void build(int node,int l,int r){
if(l==r-1){
id[l]=node;
seg[node].l.pb({});
seg[node].r.pb({});
seg[node].l[0]=seg[node].r[0]={1ll<<a[l],l};
seg[node].res=inf;
return;
}
int m=(l+r)>>1;
build(node*2,l,m);
build(node*2+1,m,r);
merge(node);
}
void update(int pos,int v){
int node=id[pos];
seg[node].l[0]=seg[node].r[0]={1ll<<v,pos};
seg[node].res=inf;
node>>=1;
while(node){
merge(node);
node>>=1;
}
}
};
signed main(){
_3Pxrs5V;
int n,k,q;
cin>>n>>k>>q;
rep(i,n){
cin>>a[i];
a[i]-=1;
}
tournament seg(n,k);
// print(seg.seg[1].res);
rep(_,q){
int t;
cin>>t;
if(t==1){
int i,v;
cin>>i>>v;
i-=1,v-=1;
seg.update(i,v);
}else{
print(seg.seg[1].res);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
920 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
916 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
