Submission #202519

#	Time	Username	Problem	Language	Result	Execution time	Memory
202519		vanic	Nekameleoni (COCI15_nekameleoni)	C++14	28 / 140	3094 ms	108636 KiB

nekameleoni

#include <iostream>
#include <cstdio>
#include <math.h>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <array>

using namespace std;

const int maxn=1e5+5, Log=17, pot=(1<<Log);
const int inf=1e9;

struct tournament1{
	pair < int, int > t[pot*2];
	tournament1(){
		for(int i=0; i<pot*2; i++){
			t[i]={inf, -inf};
		}
	}
	void update(int x, int val){
		t[x]={val, val};
		for(x/=2; x>0; x/=2){
			t[x].first=min(t[x*2].first, t[x*2+1].first);
			t[x].second=max(t[x*2].second, t[x*2+1].second);
		}
	}
	void reset(int x){
		t[x]={inf, -inf};
		for(x/=2; x>0; x/=2){
			t[x].first=min(t[x*2].first, t[x*2+1].first);
			t[x].second=max(t[x*2].second, t[x*2+1].second);
		}
	}
	int query(int L, int D, int x, int l, int d, bool p){
		if(L>=l && D<=d){
			if(p){
				return t[x].second;
			}
			else{
				return t[x].first;
			}
		}
		int lijeva, desna;
		if(p){
			lijeva=-inf;
			desna=-inf;
		}
		else{
			lijeva=inf;
			desna=inf;
		}
		if((L+D)/2>=l){
			lijeva=query(L, (L+D)/2, x*2, l, d, p);
		}
		if((L+D)/2+1<=d){
			desna=query((L+D)/2+1, D, x*2+1, l, d, p);
		}
		if(p){
			return max(lijeva, desna);
		}
		else{
			return min(lijeva, desna);
		}
	}
};

struct tournament2{
	pair < int, int > t[pot*2];
	pair < int, int > t1[pot*2];
	int prop[pot*2];
	bool jesam[pot*2];
	tournament2(){
		for(int i=0; i<pot*2; i++){
			t[i]={-inf, inf};
			t1[i]={inf, -inf};
		}
	}
	void propagate(int x, int L){
		if(jesam[x]){
			t[x]={prop[x], L};
			t1[x]={prop[x], prop[x]};
			if(x<pot){
				jesam[x*2]=1;
				jesam[x*2+1]=1;
				prop[x*2]=prop[x];
				prop[x*2+1]=prop[x];
			}
			jesam[x]=0;
		}
	}
	void update(int x, pair < int, int > val){
		int br=0, x1=x;
		while(x1<pot){
			x1*=2;
			br++;
		}
//		cout << "Update " << x-pot << " " << val.first << endl;
		propagate(x, x1-pot);
		t[x]=val;
		t1[x]={val.first, val.first};
		for(x/=2; x>0; x/=2){
			propagate(x*2, x1-pot);
			propagate(x*2+1, x1-pot+(1<<br));
			t1[x].first=min(t1[x*2].first, t1[x*2+1].first);
			t1[x].second=max(t1[x*2].second, t1[x*2+1].second);
			if(t[x*2].second-t[x*2].first>t[x*2+1].second-t[x*2+1].first){
				t[x]=t[x*2+1];
			}
			else{
				t[x]=t[x*2];
			}
			br++;
		}
	}
	void update1(int L, int D, int x, int l, int d, int val){
		propagate(x, L);
		if(L>=l && D<=d){
			update(x, {val, L});
			if(x<pot){
				prop[x*2]=val;
				prop[x*2+1]=val;
				jesam[x*2]=1;
				jesam[x*2+1]=1;
			}
			return;
		}
		if((L+D)/2>=l){
			update1(L, (L+D)/2, x*2, l, d, val);
		}
		if((L+D)/2+1<=d){
			update1((L+D)/2+1, D, x*2+1, l, d, val);
		}
	}
	int query(int val){
		int x=1;
		int L=0;
		int br=16;
		propagate(1, L);
//		cout << "Query\n";
		while(x<pot){
			propagate(x*2, L);
			propagate(x*2+1, L+(1<<br));
//			cout << t1[x].second << endl;
			if(t1[x*2].second>val){
				x*=2;
			}
			else{
				x=x*2+1;
				L+=(1<<br);
			}
			br--;
		}
		return x-pot;
	}
};


tournament1 s[50];
tournament2 T;
int l[maxn];
set < pair < int, int > > red;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m, k;
	cin >> n >> k >> m;
	for(int i=0; i<n; i++){
		cin >> l[i];
		l[i]--;
		s[l[i]].update(i+pot, i);
	}
	int x, y, z;
	int mini;
	bool p;
	for(int i=0; i<n; i++){
		mini=inf;
		p=1;
		for(int j=0; j<k; j++){
			x=s[j].query(0, pot-1, 1, 0, i, 1);
			if(x==-inf){
				p=0;
				break;
			}
			mini=min(mini, x);
		}
		if(p){
//			cout << "update " << i << endl;
			T.update(i+pot, {mini, i});
		}
	}
	int prosli, iduci;
	int neki;
	pair < int, int > pa;
	for(int i=0; i<m; i++){
		cin >> x;
		if(x==1){
			cin >> y >> z;
			y--;
			z--;
			if(y==n-1){
				prosli=n;
			}
			else{
				prosli=s[l[y]].query(0, pot-1, 1, y+1, n-1, 0);
			}
			if(prosli==inf){
				prosli=n;
			}
			prosli--;
			if(y-1==-1){
				iduci=-inf;
			}
			else{
				iduci=s[l[y]].query(0, pot-1, 1, 0, y-1, 1);
			}
			neki=T.query(iduci);
//			cout << neki << " " << prosli << " " << iduci << '\n';
			if(neki<prosli){
				T.update1(0, pot-1, 1, neki, prosli, iduci);
			}
			s[l[y]].reset(y+pot);
			s[z].update(y+pot, y);
			l[y]=z;
			if(y!=n-1){
				prosli=s[z].query(0, pot-1, 1, y+1, n-1, 0);
				if(prosli==inf){
					prosli=n;
				}
				prosli--;
				for(int j=0; j<k; j++){
					red.insert({s[j].query(0, pot-1, 1, 0, y, 1), s[j].query(0, pot-1, 1, y+1, prosli, 0)-1});
				}
				iduci=y+1;
				while(!red.empty()){
					pa=*red.begin();
					red.erase(red.begin());
					if(pa.second==inf-1){
						pa.second=prosli;
					}
					if(pa.second>=iduci){
						T.update1(0, pot-1, 1, iduci, pa.second, pa.first);
						iduci=pa.second+1;
					}
				}
			}
			mini=inf;
			for(int j=0; j<k; j++){
				mini=min(mini, s[j].query(0, pot-1, 1, 0, y, 1));
			}
			T.update1(0, pot-1, 1, y, y, mini);
		}
		else{
//			cout << T.t[1].first << " " << T.t[1].second << '\n';
			if(T.t[1].first==-inf){
				cout << -1 << '\n';
			}
			else{
				cout << T.t[1].second-T.t[1].first+1 << '\n';
			}
		}
	}
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14