Submission #202343

#	Time	Username	Problem	Language	Result	Execution time	Memory
202343		vanic	Nekameleoni (COCI15_nekameleoni)	C++14	0 / 140	3087 ms	107640 KiB

nekameleoni

#include <math.h>
#include <algorithm>
#include <cstdio>
#include <set>
#include <queue>

using namespace std;

const int maxn=1e5+5, pot=131072;
const int inf=1e9;

int n, k, m;

struct tournament1{
	pair < int, int > t[pot*2];
	tournament1(){
		for(int i=0; i<pot*2; i++){
			t[i].first=inf;
			t[i].second=-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 resetiraj(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].first;
			}
			else{
				return t[x].second;
			}
		}
		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 min(lijeva, desna);
		}
		else{
			return max(lijeva, desna);
		}
	}
};

struct tournament2{
	pair < int, int > t[pot*2];
	int prop[pot*2];
	int prop2[pot*2];
	bool imam[pot*2], imam2[pot*2];
	tournament2(){
		for(int i=0; i<pot*2; i++){
			t[i]={-inf, i};
			imam[i]=0;
			imam2[i]=0;
		}
	}
	void propagate(int x, int L){
		if(imam[x]){
			t[x]={prop[x], L};
			if(x<pot){
				imam[x*2]=1;
				prop[x*2]=prop[x];
				imam[x*2+1]=1;
				prop[x*2+1]=prop[x];
			}
			imam2[x*2]=0;
			imam2[x*2+1]=0;
			imam[x]=0;
			prop[x]=0;
		}
		else if(imam2[x]){
			if(prop2[x]<=t[x].first){
				t[x]={prop2[x], L};
			}
			if(x<pot){
				if(imam2[x*2]){
					prop2[x*2]=min(prop2[x*2], prop2[x]);
				}
				else{
					prop2[x*2]=prop2[x];
					imam2[x*2]=1;
				}
				if(imam2[x*2+1]){
					prop2[x*2+1]=min(prop2[x*2+1], prop2[x]);
				}
				else{
					prop2[x*2+1]=prop2[x];
					imam2[x*2+1]=1;
				}
				imam[x*2]=0;
				imam[x*2+1]=0;
			}
			imam2[x]=0;
			prop2[x]=0;
		}
	}
	void update(int x, pair < int, int > val){
//		printf("update %d %d\n", val.first, val.second);
		int x1=x;
		int br=0;
		while(x1<pot){
			x1*=2;
			br++;
		}
//		printf("granice %d %d\n", x1-pot, x1-pot+(1<<(br+1))-1);
		propagate(x, x1-pot);
		t[x]=val;
		for(x/=2; x>0; x/=2){
			propagate(x*2, x1-pot);
			propagate(x*2+1, x1-pot+(1<<br));
			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++;
		}
//		printf("a sad je: %d %d\n", t[1].first, t[1].second);
	}
	void update1(int L, int D, int x, int l, int d, int val, bool p){
		propagate(x, L);
		if(L>=l && D<=d){
			if(p){
				update(x, {val, L});
				if(x<pot){
					propagate(x*2, L);
					propagate(x*2+1, (L+D)/2+1);
					prop[x*2]=val;
					imam[x*2]=1;
					prop[x*2+1]=val;
					imam[x*2+1]=1;
				}
			}
			else{
//				printf("updateam %d %d %d %d\n", L, D, val, t[x].first);
				if(val<=t[x].first){
//					printf("in\n");
					update(x, {val, L});
				}
				if(x<pot){
					propagate(x*2, L);
					propagate(x*2+1, (L+D)/2+1);
					prop2[x*2]=val;
					imam2[x*2]=1;
					prop2[x*2+1]=val;
					imam2[x*2+1]=1;
				}
			}
			return;
		}
		if((L+D)/2>=l){
			update1(L, (L+D)/2, x*2, l, d, val, p);
		}
		if((L+D)/2+1<=d){
			update1((L+D)/2+1, D, x*2+1, l, d, val, p);
		}
	}
};


tournament1 s[50];
tournament2 T;
queue < pair < int, int > > red;

int main(){
	int lis[maxn];
	scanf("%d%d%d", &n, &k, &m);
	int x;
	for(int i=0; i<n; i++){
		scanf("%d", &x);
		x--;
		lis[i]=x;
		s[x].update(i+pot, i);
//		printf("%d\n", s[x].t[1].first);
	}
	int mini;
	bool p;
	for(int i=0; i<n; i++){
		mini=1e9;
		p=1;
		for(int j=0; j<k; j++){
			x=s[j].query(0, pot-1, 1, 0, i, 1);
//			printf("%d ", x);
			if(x==-1){
				p=0;
				break;
			}
			mini=min(mini, x);
		}
//		printf("\n");
		if(p){
//			printf("updateam\n");
			T.update(i+pot, {mini, i});
		}
	}
	int y, z;
//	int iduci;
//	int sad;
	pair < int, int > pa;
	int naj;
	for(int i=0; i<m; i++){
		scanf("%d", &x);
		if(x==1){
			scanf("%d%d", &y, &z);
			y--;
			z--;
/*			if(y==n-1){
				iduci=n;
			}
			else{
				iduci=s[lis[y]].query(0, pot-1, 1, y+1, n-1, 0);
			}
			if(iduci==inf){
				iduci=n;
			}
			iduci--;
			if(y==0){
				y=-1;
			}
			else{
				sad=s[lis[y]].query(0, pot-1, 1, 0, y-1, 1);
			}
//			printf("%d %d\n", iduci, sad);
			T.update1(0, pot-1, 1, sad+1, iduci, sad, 0);*/
//			printf("prosao\n");
			s[lis[y]].resetiraj(y+pot);
//			printf("kaj %d\n", lis[y]);
			s[z].update(y+pot, y);
			lis[y]=z;
//			printf("sumnjivo %d\n", s[1].t[2+pot].first);
			if(y<n-1){
				naj=0;
				for(int j=0; j<k; j++){
					pa={s[j].query(0, pot-1, 1, y+1, n-1, 0), j};
					red.push(pa);
					naj=max(naj, pa.first);
				}
//				printf("pa %d\n", naj);
				if(naj!=inf){
					T.update1(0, pot-1, 1, y+1, naj-1, inf, 1);
				}
				else{
					T.update1(0, pot-1, 1, y+1, n-1, inf, 1);
				}

				while(!red.empty()){
					pa=red.front();
					red.pop();
					if(pa.first==inf){
//						printf("USAAAO\n");
						T.update1(0, pot-1, 1, y+1, n-1, s[pa.second].query(0, pot-1, 1, 0, y, 1), 0);
					}
					else{
						if(pa.first-1>=y+1){
							T.update1(0, pot-1, 1, y+1, pa.first-1, s[pa.second].query(0, pot-1, 1, 0, y, 1), 0);
						}
					}
//					printf("na %d %d %d\n", pa.first, pa.second, s[pa.second].query(0, pot-1, 1, 0, y, 1));
				}
			}

			T.update1(0, pot-1, 1, y, y, inf, 1);
			for(int j=0; j<k; j++){
				T.update1(0, pot-1, 1, y, y, s[j].query(0, pot-1, 1, 0, y, 1), 0);
//				printf("sad %d %d\n", j, s[j].query(0, pot-1, 1, 0, y, 1));
			}
		}
		else{
//			printf("%d %d\n", T.t[1].first, T.t[1].second);
//			printf("%d %d\n", T.t[3+pot].first, T.t[3+pot].second);
			if(T.t[1].first==-inf){
				printf("%d\n", -1);
			}
			else{
				printf("%d\n", T.t[1].second-T.t[1].first+1);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

nekameleoni.cpp: In function 'int main()':
nekameleoni.cpp:192:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:195:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
nekameleoni.cpp:227:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
nekameleoni.cpp:229:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &y, &z);
    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 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