Submission #373732

#	Time	Username	Problem	Language	Result	Execution time	Memory
373732		ArKCa	Nekameleoni (COCI15_nekameleoni)	C++17	28 / 140	3080 ms	13376 KiB

nekameleoni

#include<bits/stdc++.h>
#define int long long 
#define N 100005
#define pb push_back
#define f1 first
#define s2 second
#define PII pair<int,int>
#define PIII pair<int,PII>


using namespace std;

int n,k,m,ans;
int dp[55][55][55];
PII dizi[N];
set<int>s[100];
set<int>::iterator it,it1,it2;
multiset<int>anss;
multiset<int>::iterator mit;

void dpf(int l,int r,int u,int i,int ekle,bool shet){
	set<int>::iterator it,it1,it2,sol,sag;
	if(u==dizi[i].f1){dpf(l,r,u+1,i,ekle,shet);return;}
	if(dp[l][r][u]==0)return;
	// printf("gir%lld %lld %lld %lld %lld\n",l,r,u,i,ekle );
	if(u==k+1){
		dp[l][r][u]=0;
		it1=s[l].upper_bound(i);
		it1--;
		// //printf("%lld\n", *it1);
		it2=s[r].lower_bound(i);
		it=it2;
		if(1){
		if(r!=0  && l!=0 && it2!=s[r].begin() &&   (*(--it2)>*it1))return;
		it2=it;
		if( (++it1)!=s[l].end()&& l!=0 && r!=0 && (*(it1)<*it2))return;
		it1--;}
		int tot;
		tot=i-(*(it1));
		tot+=(*(it2))-i;
		tot++;
		if(l==0){
			sag=s[dizi[i].f1].upper_bound(i);
			if(sag!=s[dizi[i].f1].end() && *sag<*it2 )return;
		}
		if(r==0){
			sol=s[dizi[i].f1].lower_bound(i);
			if(sol!=s[dizi[i].f1].begin() &&*(--sol)>*it1 )return;
		}
		// //printf("%lld %lld %lld\n",i-(*(it1)),(*(it2))-i,tot );
		// printf("sil %lld %lld %lld %lld %lld %lld\n",l,r,u,i,ekle,tot );
		// if(tot==19)printf("aaaa%lld %lld\n",ekle,ans );
		if(ekle)
			anss.insert(tot);
		else{
			it=anss.find(tot);
			if(it!=anss.end())
			anss.erase(it);
			// elsed
		}
		return;
	}
	dp[l][r][u]=0;
	it=s[u].lower_bound(i);
	//printf("it:%lld\n",*it );
	if(it!=s[u].end()){
		if(*it>=*s[r].lower_bound(i)){
		//printf("sa %lld %lld %lld %lld %lld %lld\n",l,u,u,i,ekle,*it );
			dpf(l,u,u+1,i,ekle,shet);
		}
		else{
		//printf("sag%lld %lld %lld %lld %lld %lld\n",l,r,u,i,ekle,*it );
			dpf(l,r,u+1,i,ekle,shet);

		}

	}
	if(it!=s[u].begin()){
		//printf("%lld %lld\n",*s[u].begin(),*it );
		it--;
		it1=s[l].upper_bound(i);
		it1--;
		if(*it<=*it1){
		//printf("so %lld %lld %lld %lld %lld %lld %lld\n",u,r,u,i,ekle,*it,*it1 );

			dpf(u,r,u+1,i,ekle,shet);
		}
		else{
		//printf("sol%lld %lld %lld %lld %lld %lld %lld\n",l,r,u,i,ekle,*it,*it1 );

			dpf(l,r,u+1,i,ekle,shet); 
		} 
	} 
	return;
}


int32_t main(){
	// freopen("a.gir","r",stdin);
	// freopen("a.cik","w",stdout);

	scanf("%lld %lld %lld",&n,&k,&m);
	for(int i=0;i<n;i++){
		scanf("%lld",&dizi[i].f1);
		s[dizi[i].f1].insert(i);
		dizi[i].s2=1;
	}
	// printf("%lld\n", dizi[970].f1);
	int mx=0;
	for(int i=0;i<=n;i++){
		s[0].insert(i);
	}
	for(int i=0;i<n;i++){
		mx=0;
		for(int j=1;j<=k;j++){
			if(j==dizi[i].f1)continue;
			it=s[j].lower_bound(i);
			if(it==s[j].end()){
				mx=-1;
				break;
			}
			mx=max(mx,*it-i+1);
		}
		if(mx!=-1){
			it=s[dizi[i].f1].upper_bound(i);
			if(it==s[dizi[i].f1].end() || *it-i+1>mx){
				// printf("%lld\n", i);
				anss.insert(mx);
			}
		}
	}
	anss.insert(INT_MAX);
	int a,b,c;
	for(int i=0;i<m;i++){
		// for(mit=anss.begin();mit!=anss.end();mit++){
		// 	printf("%lld ",*mit );
		// }
		// printf("\n");
		ans=i;
		scanf("%lld",&a);
		if(a==2){
			// //printf("%lu ",anss.size() );
			printf("%lld\n",*(anss.begin())==INT_MAX?-1:*(anss.begin()) );
		}
		else{
			// for(mit=anss.begin();mit!=anss.end();mit++){
			// 	printf("%lld ",*mit );
			// }
			// printf("\n");
			scanf("%lld %lld",&b,&c);
			b--;
			memset(dp,-1,sizeof(dp));
		    dpf(0,0,1,b,0,dizi[i].s2);
		    dizi[i].s2=0;
			// //printf("~~%lld\n",dizi[b].f1);
			s[dizi[b].f1].erase(b);
			dizi[b].f1=c;	
			s[c].insert(b);
			// // //printf("~~%lld\n",dizi[b].f1);
			memset(dp,-1,sizeof(dp));
			// for(mit=anss.begin();mit!=anss.end();mit++){
			// 	printf("%lld ",*mit );
			// }
			// printf("\n");
			dpf(0,0,1,b,1,dizi[i].s2);
			// for(mit=anss.begin();mit!=anss.end();mit++){
			// 	printf("%lld ",*mit );
			// }
			// printf("\n\n");
			//printf("---------bitti\n");
			// printf("\n");
			// for(it=s[1].begin();it!=s[1].end();it++){
			// 	printf("%lld ",*it );
			// }

			// printf("\n\n");
		}
	}
}

Compilation message (stderr)

nekameleoni.cpp: In function 'int32_t main()':
nekameleoni.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |  scanf("%lld %lld %lld",&n,&k,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |   scanf("%lld",&dizi[i].f1);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  140 |   scanf("%lld",&a);
      |   ~~~~~^~~~~~~~~~~
nekameleoni.cpp:150:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |    scanf("%lld %lld",&b,&c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

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