Submission #1252466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252466		nhnguyen14	Nekameleoni (COCI15_nekameleoni)	C++20	0 / 140	1791 ms	7592 KiB

nekameleoni

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define ii pair<int,int>
#define BIT(mask,x) (((mask)>>(x))&(1))
#define MASK(x) ((LL)(1)<<(x))
#define FOR(i,a,b) for(int i = (a),_b=(b); i<=_b;++i)
#define FORD(i,a,b) for(int i =(a),_b=(b);i>=_b;--i)

template<class X,class Y>
	bool maximize(X &x,Y y){
		if (x<y) return x=y,true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x,Y y){
		if (x>y) return x=y,true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
	LL Rand(LL l,LL r){
		return uniform_int_distribution<LL>(l,r)(rng);
	}
	
const int N = (int) 1e5;
const int MAXK = (int)50;
const int inf = 1e9;
	int a[N+2] ;
	int n , m , k;
	
class IT{
	public:
		vector<int>st;
		void load_size(int _n){
			st = vector<int>(_n*4+2,0);
			return;
		}
		#define lef(id) id*2
		#define rig(id) id*2+1
		void upd(int id,int l,int r,int pos,int val){
			if (l==r) st[id] = val;
			else {
				int m = (l+r)/2;
				if (pos <= m) upd(lef(id) , l , m , pos , val);
					else upd(rig(id) , m + 1 , r , pos , val);
				st[id] = max(st[id*2],st[id*2+1]);
			}
		}
		int Get(int id,int l,int r,int need_l,int need_r){
			if (l > need_r || r < need_l) return -inf;
			if (need_l <= l && r <= need_r) return st[id];
			int m = (l+r)/2;
			return max(Get(lef(id),l,m,need_l,need_r) , Get(rig(id),m+1,r,need_l,need_r));
		}
};
IT res;
IT tmp;
set<int>pos[MAXK+2];
int ans[N+2] = {};

int Get_ans(void){
	int ans = -res.st[1];
	if (ans==inf) return -1; else return ans;
}

int Find_lower(int p,int need_p){
	auto it = pos[p].upper_bound(need_p);
	if (it==pos[p].begin()) return -1;	
		else return *(--it);
}
int Find_upper(int p,int need_p){
	auto it = pos[p].lower_bound(need_p);
	if (it==pos[p].end()) return inf; else 
		return *it;
}

int quason[MAXK+2] = {};

	void del(int need_p){
		FOR(i,1,k){
			int p = Find_lower(i,need_p);
			if (p==-1) continue;
			if (p + ans[p] - 1 < need_p) continue;
			res.upd(1,1,n,p,-inf);
			ans[p] = inf;
		}
		return;
	}

void process(int need_p,int val){
	vector<pair<int,int>>v;
	tmp.load_size(k);
	del(need_p);
		pos[a[need_p]].erase(pos[a[need_p]].find(need_p));
		a[need_p] = val;
		res.upd(1,1,n,need_p,-inf);
		ans[need_p] = inf;
		pos[a[need_p]].insert(need_p);
	FOR(i,1,k){
		int p = Find_lower(i , need_p);
		int tt = Find_upper(i , need_p);
		if (p==-1) tmp.upd(1,1,k,i,tt);
			else {
				if (ans[p] + p - 1 < need_p) {
					tmp.upd(1,1,k,i,tt);
					continue;
				}
				v.push_back({p,i});
				quason[i] = tt;
				tmp.upd(1,1,k,i,p);
			}
	}
	sort(v.begin() , v.end());
	for(auto&x : v) {
		int tt = tmp.st[1];
		if (tt==inf) ans[x.first] = inf; else {
			ans[x.first] = tmp.st[1] - x.first + 1;
			res.upd(1,1,n,x.first,-ans[x.first]);
			tmp.upd(1,1,k,x.second,quason[x.second]);
		}
	}
	return;
	
}

int cnt[MAXK+2] = {};
	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n >> k >> m;
		FOR(i,1,n) cin >> a[i];
		FOR(i,1,n) pos[a[i]].insert(i);
		set<int>intial;
		res.load_size(n);
		for(int i = 1 , j = 1; i <= n; ++i){
			while (j <= n && intial.size() != k) {
				if (cnt[a[j]]==0) intial.insert(a[j]);
				cnt[a[j]]++;
				++j;
			}
			if (intial.size() != k) ans[i] = inf; else ans[i] = j - i;
			--cnt[a[i]];
			if (cnt[a[i]]==0) intial.erase(a[i]);
			res.upd(1,1,n,i,-ans[i]);
		}
		while(m--){
			int t; cin>>t;
			if (t==2) cout<<Get_ans()<<'\n';
				else {
					int p,val; cin>>p>>val;
					process(p,val);
				}
		}
	return 0;
}

Compilation message (stderr)

nekameleoni.cpp: In function 'int main()':
nekameleoni.cpp:138:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:139:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 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