Submission #1252492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252492		nhnguyen14	Nekameleoni (COCI15_nekameleoni)	C++20	140 / 140	2227 ms	11904 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] ;
	set<int>pos[MAXK+2];
	int n , m , k;
	
class IT{
	public:
		vector<int>st , mn , lazy;;
		vector<int>gt;
		void load_size(int _n){
			st = vector<int>(_n*4+2,0);
			mn = vector<int>(_n*4+2,0);
			lazy = vector<int>(_n*4+2,-1);
			gt = vector<int>(_n*4+2,0);
			return;
		}
		void build(int id,int l,int r){
			if (l==r) {
				mn[id] = st[id] = l;
				gt[id] = st[id] - mn[id] + 1;
			} else {
				int m = (l+r)/2;
				build(id*2,l,m);
				build(id*2+1,m+1,r);
				mn[id] = max(mn[id*2],mn[id*2+1]);
				st[id] = max(st[id*2],st[id*2+1]);
				
				gt[id] = min(gt[id*2],gt[id*2+1]);
			}
		}
		
		void pushdown(int id){
			int &t = lazy[id];
			if (t==-1) return;
				st[id*2] = st[id*2+1] = lazy[id*2] = lazy[id*2+1] = t;
				gt[id*2] = st[id*2] - mn[id*2] + 1;
				gt[id*2+1] = st[id*2+1] - mn[id*2+1] + 1;
			t = -1;
			return;
		}
		
		void update(int id,int l,int r,int need_l,int need_r,int val){
			if (l > need_r || r  < need_l) return;
			if (need_l <= l && r <= need_r ){
				st[id] = val;
				gt[id] = st[id] - mn[id] + 1;
				lazy[id] = val;
				return;
			}
			int m = (l+r)/2;
			pushdown(id);
			update(id*2, l , m , need_l,need_r , val);
			update(id*2+1, m+1 , r , need_l,need_r , val);
			st[id] = max(st[id*2],st[id*2+1]);
			gt[id] = min(gt[id*2],gt[id*2+1]);
		}
		
		int Get(int id,int l,int r,int need_l , int need_r){
			if (l > need_r || l < need_l) return inf;
			if (need_l <= l && r <= need_r) return gt[id];
			int m = (l+r)/2;
			pushdown(id);
			return min(Get(id*2,l,m,need_l,need_r) , Get(id*2+1,m+1,r,need_l,need_r));
		}
		int Get_mx(int id,int l,int r,int u,int v){
			if (l>v||r<u) return 0;
			if (u<=l&&r<=v) return st[id];
			int m = (l+r)/2;
			pushdown(id);
			return max(Get_mx(id*2,l,m,u,v),Get_mx(id*2+1,m+1,r,u,v));
		}
	};
	
	IT st;

	int Get_lowest(int need_p){
		int low = 1 , high = need_p , pos = 1;
		while (low<=high){
			int mid = (low+high)/2;
			if (st.Get_mx(1,1,n,mid,mid) >= need_p) {
				pos = mid , high = mid - 1;
			}
			else low = mid + 1;
		}
		return pos;
	}
	
	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 process(int need_p,int v){
//		FOR(i,1,n) cout<<st.Get_mx(1,1,n,i,i)<<' '; cout<<'\n';
		int lowest = Get_lowest(need_p);
			st.update(1,1,n,lowest , need_p , inf);
			pos[a[need_p]].erase(need_p);
			a[need_p] = v;
			pos[a[need_p]].insert(need_p);
			
		int mx = need_p;
		vector<pair<int,int>>vs;
			
		FOR(i,1,k){
			int p = Find_lower(i , need_p) ;
			int tt = Find_upper(i , need_p) ;
			if (p == -1) maximize(mx , tt);
				else {
					if (st.Get_mx(1,1,n,p,p) < need_p) maximize(mx , tt);
					else {
						vs.push_back({p,i});
						quason[i] = tt;
					}
				}
		}
		vs.push_back({lowest-1,0});
		sort(vs.begin() , vs.end());
		for(int i = 1; i < vs.size(); ++i){
			st.update(1,1,n,vs[i-1].first+1,vs[i].first,mx);
			maximize(mx , quason[vs[i].second]);
		}
		return;
	}
	
int cnt[MAXK+2] = {};
	int Get_ans(){
		int x = st.gt[1];
		if (x>n) return -1; else return x;
	}
	
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;
		st.load_size(n);
		st.build(1,1,n);
		FOR(i,1,n) cin>>a[i];
		FOR(i,1,n) pos[a[i]].insert(i);
		int ss = 0;
		for(int i = 1 , j = 1; i <= n; ++i){
			while (j <= n && ss != k){
				if (cnt[a[j]]==0) ++ss;
				++cnt[a[j]];
				++j;
			}
//			cout<<i<<' '<<j-1<<' '<<ss<<' '<<k<<'\n';
			if (ss==k) {
				st.update(1,1,n,i,i,j-1); 
//				cout<<i<<' '<<st.Get_mx(1,1,n,i,i)<<'\n';
			}else st.update(1,1,n,i,i,inf);
			--cnt[a[i]];
			if (cnt[a[i]]==0) --ss;
		}
		while(m--){
			int t; cin>>t;
			if (t==2) cout<<Get_ans()<<'\n';
			else {
				int p,v; cin>>p>>v;
				process(p,v);
			}
		}

	return 0;
}

Compilation message (stderr)

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

• 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