oj.uz

Submission #605380

# Submission time Handle Problem Language Result Execution time Memory
605380 2022-07-25T16:44:46 Z inksamurai Nekameleoni (COCI15_nekameleoni) C++17
0 / 140
 1022 ms 54848 KB 
#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=340011; // 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);
		}
	}
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21204 KB Output is correct
2 Incorrect 17 ms 21068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 21600 KB Output is correct
2 Incorrect 28 ms 21588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 22036 KB Output is correct
2 Incorrect 33 ms 22040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 27776 KB Output is correct
2 Incorrect 667 ms 44580 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 39472 KB Output is correct
2 Incorrect 617 ms 52852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 35372 KB Output is correct
2 Incorrect 641 ms 48860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 42248 KB Output is correct
2 Incorrect 701 ms 50176 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 41372 KB Output is correct
2 Incorrect 687 ms 52004 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 54808 KB Output is correct
2 Incorrect 746 ms 53960 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 54848 KB Output is correct
2 Incorrect 728 ms 54008 KB Output isn't correct
3 Halted 0 ms 0 KB -