Submission #1038905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038905		vjudge1	Nekameleoni (COCI15_nekameleoni)	C++17	42 / 140	3101 ms	166228 KiB

nekameleoni

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=1e5+5;
int const K=52;
int const inf=1e6+7;

int val[4*N];
int F[4*N][K],L[4*N][K];
int arr[N];
int n,m,k;

void recalculate(int node){
	val[node]=min(val[(node*2)+1],val[(node*2)+2]);
	for(int i=1;i<=k;i++){
		F[node][i]=F[(node*2)+1][i];
		if(F[(node*2)+1][i]==-inf)
			F[node][i]=F[(node*2)+2][i];
		L[node][i]=L[(node*2)+2][i];
		if(L[node][i]==inf)
			L[node][i]=L[(node*2)+1][i];
	}
	vector<pair<int,int>> v;
	for (int i = 1; i <=k; ++i){
		if(L[node*2+1][i]==inf)
			v.push_back({-inf,i});
		else
			v.push_back({L[(node*2)+1][i],i});
	}
	sort(v.begin(), v.end());
	int maxa=v[k-1].first;
	for(int i=1;i<k;i++){
		if(F[(node*2)+2][v[i-1].second]==-inf)
			maxa=inf;
		maxa=max(F[(node*2)+2][v[i-1].second],maxa);
		val[node]=min(val[node],1+(maxa-v[i].first));
	}
	// if(node>0)
	// 	return;
	// cout<<node<<' '<<val[node]<<endl;
	// for (int i = 0; i <k; ++i)
	// 	cout<<v[i].first<<' '<<v[i].second<<endl;
	// cout<<node<<' '<<val[node]<<endl;
}

void update(int node, int left, int right, int ind, int v) {
    if (left == right){//set
    	val[node]=inf;
		for (int j = 1; j <=k; ++j){
			F[node][j]=-inf;
			L[node][j]=inf;
		}
		F[node][v]=ind;
		L[node][v]=ind;
		if(k==1 && v==1)
			val[node]=1;
		// cout<<node<<' '<<val[node]<<endl;
		// for (int i = 1; i <=k; ++i)
		// 	cout<<F[node][i]<<' '<<L[node][i]<<endl;
		// cout<<node<<' '<<val[node]<<endl;
    }
    else {
        int middle = (left + right) / 2;
        if (ind <= middle)//we need to update the left son
            update(2 * node + 1, left, middle, ind, v);
        else
            update(2 * node + 2, middle + 1, right, ind, v);
        //after updating said son, recalculate the current segment
        recalculate(node);
    }
}

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cin>>n>>k>>m;
	for (int i = 1; i <=n; ++i)
		cin>>arr[i];
	for (int i = 0; i <=4*(n+2); ++i)
	{
		val[i]=inf;
		for (int j = 0; j <=k; ++j){
			F[i][j]=-inf;
			L[i][j]=inf;
		}
	}
	for (int i = 1; i <=n; ++i){
		update(0,1,n,i,arr[i]);
		// cout<<endl;
	}
	// cout<<val[0]<<endl;
	// for (int i = 1; i <=k; ++i)
	// 	cout<<F[0][i]<<' '<<L[0][i]<<endl;
	// cout<<val[0]<<endl;
	while(m--){
		int t;
		cin>>t;
		if(t==1){
			int p,v;
			cin>>p>>v;
			update(0,1,n,p,v);
		}
		else{
			if(val[0]>n)
				cout<<-1<<endl;
			else
				cout<<val[0]<<endl;
		}
	}
	return 0;
}

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