oj.uz

Submission #1038905

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

# Verdict Execution time Memory Grader output
1 Correct 25 ms 8024 KB Output is correct
2 Correct 21 ms 6152 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 7512 KB Output is correct
2 Correct 68 ms 7516 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 8540 KB Output is correct
2 Correct 145 ms 12120 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1851 ms 90708 KB Output is correct
2 Execution timed out 3101 ms 157076 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1962 ms 69352 KB Output is correct
2 Execution timed out 3031 ms 135784 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2341 ms 109140 KB Output is correct
2 Execution timed out 3070 ms 142276 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2522 ms 103952 KB Output is correct
2 Execution timed out 3080 ms 153348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3045 ms 166224 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 3044 ms 166228 KB Time limit exceeded
2 Halted 0 ms 0 KB -