Submission #1173385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173385		nuutsnoynton	Nekameleoni (COCI15_nekameleoni)	C++20	140 / 140	615 ms	76608 KiB

nekameleoni

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair < ll, ll >;
const ll N =2e5 + 2; 
ll T[4 * N];
vector < pll > pre[4 * N];
vector < pll > suf[4 * N];
ll a[N], k, n;
void Build(ll p, ll lo, ll hi) {
	T[p] = 1e18;
	if ( lo == hi) {
		T[p] = 1e18;
		if ( k == 1) T[p] = 1;
		pre[p].push_back(make_pair(lo, a[lo]));
		suf[p].push_back(make_pair(lo, a[lo]));
		return ;
	}
	ll i, mid = (lo + hi)/2;
	Build(2 * p, lo, mid);
	Build(2 * p + 1, mid + 1, hi);
	ll cnt[52] = {0};
	for (i =0 ; i < pre[2 *p].size(); i ++) {
		pre[p].push_back(pre[2 * p][i]);
		cnt[pre[2 * p][i].second] = 1;
	}
	for (i =0 ; i < pre[2 *p + 1].size(); i ++) {
		if ( cnt[pre[2 * p + 1][i].second] == 0) {
			pre[p].push_back(pre[2 * p + 1][i]);
		}
		cnt[pre[2 * p + 1][i].second] = 1;
	}
	for (i = 1; i <= k; i ++) cnt[i] = 0; 
	for (i =0 ; i < suf[2 *p + 1].size(); i ++) {
		suf[p].push_back(suf[2 * p + 1][i]);
		cnt[suf[2 * p + 1][i].second] = 1;
	}
	for (i =0 ; i < suf[2 *p].size(); i ++) {
		if ( cnt[suf[2 * p][i].second] == 0) {
			suf[p].push_back(suf[2 * p][i]);
		}
		cnt[suf[2 * p][i].second] = 1;
	}
	T[p] = min(T[2 *p], T[2 * p + 1]);
	ll Lo = lo;
	ll Hi =hi,cnt1 = 0;
	if ( pre[p].size() == k) {
		lo = 0;
		hi = pre[2 * p + 1].size() - 1;
		for (i = 1; i <= k; i ++) cnt[i] = 0;
		for (i = 0; i < pre[2 * p + 1].size(); i ++) {
			cnt[pre[2 * p + 1][i].second] ++;
			if ( cnt[pre[2 * p + 1][i].second] == 1) cnt1++;
		}
		while ( lo < suf[2 * p].size() && cnt1 < k) {
			cnt[suf[2 * p][lo].second] ++;
			if ( cnt[suf[2 * p][lo].second] == 1) cnt1 ++;
			lo ++;
		}
		if ( lo > 0) {
			lo --;
			cnt[suf[2 * p][lo].second] --;
		}
		while ( lo < suf[2 * p].size()) {
			cnt[suf[2 * p][lo].second] ++;
			while ( hi >= 0 && cnt[pre[2 * p + 1][hi].second] > 1) {
				cnt[pre[2 * p + 1][hi].second] --;
				hi --;
			}
			if ( hi >= 0 ) {
	//			cout << pre[2 * p + 1][hi].first << " " << suf[2 * p][lo].first << endl;
				T[p] = min(T[p], pre[2 * p + 1][hi].first - suf[2 * p][lo ].first + 1);
			}
			lo ++;
		}
	}
	
//	cout << p << " " << Lo << " "<< Hi << "R " << T[p] << endl;
	return ;
}

void Update(ll p, ll lo, ll hi, ll x, ll y)  {
	T[p] = 1e18;
	pre[p].clear();
	suf[p].clear();
	if ( lo == hi) {
		T[p] = 1e18;
		a[lo] = y;
		if ( k == 1) T[p] = 1;
		pre[p].push_back(make_pair(lo, a[lo]));
		suf[p].push_back(make_pair(lo, a[lo]));
		return ;
	}
	ll i, mid = (lo + hi)/2;
	if ( x <= mid) Update(2 * p, lo, mid, x, y);
	else Update(2 * p + 1, mid + 1, hi, x, y);
	ll cnt[52] = {0};
	for (i =0 ; i < pre[2 *p].size(); i ++) {
		pre[p].push_back(pre[2 * p][i]);
		cnt[pre[2 * p][i].second] = 1;
	}
	for (i =0 ; i < pre[2 *p + 1].size(); i ++) {
		if ( cnt[pre[2 * p + 1][i].second] == 0) {
			pre[p].push_back(pre[2 * p + 1][i]);
		}
		cnt[pre[2 * p + 1][i].second] = 1;
	}
	for (i = 1; i <= k; i ++) cnt[i] = 0; 
	for (i =0 ; i < suf[2 *p + 1].size(); i ++) {
		suf[p].push_back(suf[2 * p + 1][i]);
		cnt[suf[2 * p + 1][i].second] = 1;
	}
	for (i =0 ; i < suf[2 *p].size(); i ++) {
		if ( cnt[suf[2 * p][i].second] == 0) {
			suf[p].push_back(suf[2 * p][i]);
		}
		cnt[suf[2 * p][i].second] = 1;
	}
	T[p] = min(T[2 *p], T[2 * p + 1]);
	ll Lo = lo;
	ll Hi =hi,cnt1 = 0;
	if ( pre[p].size() == k) {
		lo = 0;
		hi = pre[2 * p + 1].size() - 1;
		for (i = 1; i <= k; i ++) cnt[i] = 0;
		for (i = 0; i < pre[2 * p + 1].size(); i ++) {
			cnt[pre[2 * p + 1][i].second] ++;
			if ( cnt[pre[2 * p + 1][i].second] == 1) cnt1++;
		}
		while ( lo < suf[2 * p].size() && cnt1 < k) {
			cnt[suf[2 * p][lo].second] ++;
			if ( cnt[suf[2 * p][lo].second] == 1) cnt1 ++;
			lo ++;
		}
		if ( lo > 0) {
			lo --;
			cnt[suf[2 * p][lo].second] --;
		}
		while ( lo < suf[2 * p].size()) {
			cnt[suf[2 * p][lo].second] ++;
			while ( hi >= 0 && cnt[pre[2 * p + 1][hi].second] > 1) {
				cnt[pre[2 * p + 1][hi].second] --;
				hi --;
			}
			if ( hi >= 0 ) {
			//	cout << pre[2 * p + 1][hi].first << " " << suf[2 * p][lo].first << endl;
				T[p] = min(T[p], pre[2 * p + 1][hi].first - suf[2 * p][lo ].first + 1);
			}
			lo ++;
		}
	}
	return ;
}

int main() {
	ll q, i, j, x, y;
	
	cin >> n >> k >> q;
	
	for (i = 1; i <= n; i ++) {
		cin >> a[i];	
	}	
	Build(1, 1, n);
	
	while (q --) {
		cin >> x;
		if ( x == 2) {
			if ( T[1] > n) cout << -1 << endl;
			else cout<< T[1] << endl;
		}
		else {
			cin >> x >> y;
			Update(1, 1, n, x, y);
		}
	}
	
	
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14