oj.uz

Submission #373407

# Submission time Handle Problem Language Result Execution time Memory
373407 2021-03-04T13:32:58 Z ArKCa Nekameleoni (COCI15_nekameleoni) C++17
0 / 140
 3000 ms 18668 KB 
#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];
PIII dizi[N];
set<int>s[100];
set<int>::iterator it,it1,it2;
multiset<int>anss;

void dpf(int l,int r,int u,int i,int ekle){
	set<int>::iterator it,it1,it2;
	//printf("gir%lld %lld %lld %lld %lld\n",l,r,u,i,ekle );
	if(u==dizi[i].f1){dpf(l,r,u+1,i,ekle);return;}
	if(dp[l][r][u]==0)return;
	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(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 sj;
		sj=i-(*(it1));
		sj+=(*(it2))-i;
		sj++;
		// //printf("%lld %lld %lld\n",i-(*(it1)),(*(it2))-i,sj );
		// //printf("sil%lld %lld %lld %lld %lld %lld\n",l,r,u,i,ekle,sj );
		if(ekle)
			anss.insert(sj);
		else{
			it=anss.find(sj);
			if(it!=anss.end())
			anss.erase(it);
		}
		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);
		}
		else{
		//printf("sag%lld %lld %lld %lld %lld %lld\n",l,r,u,i,ekle,*it );
			dpf(l,r,u+1,i,ekle);

		}

	}
	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);
		}
		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);
		}
	}
	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);
	}
	int mx=0;
	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)anss.insert(mx);
	}
	for(int i=0;i<=n;i++){
		s[0].insert(i);
	}
	anss.insert(INT_MAX);
	int a,b,c;
	for(int i=0;i<m;i++){
		scanf("%lld",&a);
		if(a==2){
			// //printf("%lu ",anss.size() );
			printf("%lld\n",*(anss.begin())==INT_MAX?-1:*(anss.begin()) );
		}
		else{
			scanf("%lld %lld",&b,&c);
			b--;
			memset(dp,-1,sizeof(dp));
		    dpf(0,0,1,b,0);
			// //printf("~~%lld\n",dizi[b].f1);
			 s[dizi[b].f1].erase(b);
			 dizi[b].f1=c;
			 s[dizi[b].f1].insert(b);
			// // //printf("~~%lld\n",dizi[b].f1);
			 memset(dp,-1,sizeof(dp));
			 dpf(0,0,1,b,1);
			//printf("---------bitti\n");
		}
	}
}

Compilation message

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

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 10860 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 3019 ms 8732 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 3050 ms 12780 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 3050 ms 11756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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