oj.uz

Submission #1038900

# Submission time Handle Problem Language Result Execution time Memory
1038900 2024-07-30T08:49:11 Z vjudge1 Nekameleoni (COCI15_nekameleoni) C++17
42 / 140
 3000 ms 166248 KB 
#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(){
	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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5976 KB Output is correct
2 Correct 25 ms 12748 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12808 KB Output is correct
2 Correct 69 ms 7516 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 14856 KB Output is correct
2 Correct 139 ms 14684 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 37876 KB Output is correct
2 Execution timed out 3039 ms 120148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1725 ms 93716 KB Output is correct
2 Execution timed out 3048 ms 159584 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1852 ms 72532 KB Output is correct
2 Execution timed out 3068 ms 138364 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2554 ms 111932 KB Output is correct
2 Execution timed out 3073 ms 144784 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2486 ms 101076 KB Output is correct
2 Execution timed out 3081 ms 153172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2960 ms 166224 KB Output is correct
2 Execution timed out 3052 ms 166224 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

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