oj.uz

Submission #339924

# Submission time Handle Problem Language Result Execution time Memory
339924 2020-12-26T11:12:11 Z Nimbostratus Nekameleoni (COCI15_nekameleoni) C++17
42 / 140
 3000 ms 1388 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 364 KB Output is correct
2 Correct 52 ms 364 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 364 KB Output is correct
2 Correct 86 ms 364 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 492 KB Output is correct
2 Correct 123 ms 364 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 1260 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 3029 ms 1260 KB Time limit exceeded
2 Halted 0 ms 0 KB -