oj.uz

Submission #604999

# Submission time Handle Problem Language Result Execution time Memory
604999 2022-07-25T12:04:02 Z inksamurai Nekameleoni (COCI15_nekameleoni) C++17
0 / 140
 3000 ms 54360 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;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=140002;
const int _k=51;

struct node{
	int res;
	int l[_k+1],r[_k+1];
};

node seg[_n];

int k; // initial k

void build(int node,int l,int r){
	seg[node].res=inf;
	rep(i,k){
		seg[node].l[i]=inf;
		seg[node].r[i]=-inf;
	}
	if(l==r-1){
		return;
	}
	int m=(l+r)>>1;
	build(node*2,l,m);
	build(node*2+1,m,r);
}

void update(int node,int l,int r,int pos,int v){
	if(l==r-1){
		rep(i,k){
			seg[node].l[i]=inf;
			seg[node].r[i]=-inf;
		}
		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);
	vec(pii) evs;
	multiset<int> mst;
	rep(i,k){
		// if(node==3) cout<<seg[node*2+1].l[i]<<" "<<seg[node*2].r[i]<<"\n";
		evs.emplace_back(seg[node*2+1].l[i],seg[node*2].r[i]);
		// mst.insert(seg[node*2].r[i]);
		seg[node].r[i]=max(seg[node*2+1].r[i],(seg[node*2].l[i]!=inf?seg[node*2].l[i]:-inf));
		seg[node].l[i]=min((seg[node*2+1].r[i]!=-inf?seg[node*2+1].r[i]:inf),seg[node*2].l[i]);
	}
	for(auto p:evs){
		if(abs(p.fi)==inf) continue;
		int _l=inf;
		for(auto np:evs){
			if(np.fi<=p.fi) continue;
			_l=min(_l,np.se);
		}
		seg[node].res=min(seg[node].res,p.fi-_l+1);
	}
	// print("\n....");
	// sort(evs.begin(), evs.end());
	// if(evs.back().fi!=inf){
	// 	seg[node].res=min(seg[node].res,evs.back().fi-evs[0].fi+1);
	// }
	// if(*prev(mst.end())!=inf){
	// 	// if(node==1){
	// 	// 	for(auto v:mst){
	// 	// 		cout<<v<<" ";
	// 	// 	}
	// 	// 	print("\n....");
	// 	// }
	// 	// print(node,*(prev(mst.end()))-*(mst.begin()));
	// 	seg[node].res=min(seg[node].res,*(prev(mst.end()))-*(mst.begin())+1);
	// }
	// rep(i,sz(evs)-1){
	// 	pii p=evs[i];
	// 	auto it=mst.find(p.se);
	// 	mst.erase(it);
	// 	int _r=evs[i].fi;
	// 	int _l=*mst.begin();
	// 	if(abs(_l)==inf or abs(_r)==inf) continue;
	// 	seg[node].res=min(seg[node].res,_r-_l+1);
	// }
	// if(node==3){
	// 	print(seg[node].res);
	// }
	// print(l,r,m,node);
}

signed main(){
_3Pxrs5V;
	int n,q;
	cin>>n>>k>>q;
	build(1,0,n);
	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";/
			}
		}
	}
	// print(seg[1].res);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 3668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 4716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 303 ms 6868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2620 ms 27400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 54320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3094 ms 54360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3100 ms 54260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3097 ms 54180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 15524 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 15432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -