Submission #339924

#	Time	Username	Problem	Language	Result	Execution time	Memory
339924		Nimbostratus	Nekameleoni (COCI15_nekameleoni)	C++17	42 / 140	3103 ms	1388 KiB

nekameleoni

#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define all(x) (x.begin() , x.end())
#define sz(x) (x.size())
#define fre freopen("in","r",stdin); freopen("out","w",stdout);
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<int> vint;

const int MAXN = 1e5;

int N,K,M;
int A[MAXN+5];

bool check(int s)
{
	int cnt[K+5];
	int inc = 0;
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=s;i++) {inc += (!cnt[A[i]]) , cnt[A[i]]++;}
	if(inc == K) return true;
	for(int i=s+1;i<=N;i++)
	{
		cnt[A[i-s]]--;
		cnt[A[i]]++;
		if(!cnt[A[i-s]]) inc--;
		if(cnt[A[i]] == 1 and A[i] != A[i-s]) inc++;
		//cout << cnt[A[1]] << " " <<  s << " " << inc << endl;
		if(inc == K) return true;		
	}
	return false;
}		

int solve()
{
	int l = 1 , r = N,mid;
	while(l < r-1)
	{
		mid = (l+r)>>1;
		if(check(mid)) r = mid;
		else l = mid+1;
	}
	if(check(l)) return l;
	if(check(r)) return r;
	return -1;
}

int32_t main()
{
	//fre;
	fast_io;
	cin >> N >> K >> M;
	for(int i=1;i<=N;i++) cin >> A[i];
	while(M--)
	{
		int opt;
		cin >> opt;
		if(opt == 2)
			cout << solve() << endl;
		else
		{
			int ind,val;
			cin >> ind >> val;
			A[ind] = val;
		}
	}
}

• 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