제출 #442129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442129		Nima_Naderi	Money (IZhO17_money)	C++14	45 / 100	1593 ms	59104 KiB

money

//In the name of GOD
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef int ll;
const ll MXN = 1e6 + 10;
ll n, ans;
ll A[MXN], cnt[MXN], blk[MXN];
set<ll> st;
bool next(ll x, ll y){
	auto itr = st.find(x);
	if(itr == st.end()) return 0;
	itr ++;
	if(itr == st.end() || *itr != y) return 0;
	return 1;
}
void relax(ll x, ll t){
	cnt[x] -= t; assert(cnt[x] >= 0);
	if(!cnt[x]){
		auto itr = st.find(x);
		st.erase(itr);
	}
}
void solve(ll m){
	if(!m) return;
	ll pnt = m - 1, last = A[m], t = 1;
	while(pnt >= 1){
		if(A[pnt] == last){
			t ++; pnt --;
			continue;
		}
		if(!next(A[pnt], last)){
			break;
		}
		if(last == A[m]){
			relax(last, t);
			t = 1, last = A[pnt];
			pnt --;
			continue;
		}
		if(t != cnt[last]) break;
		relax(last, t);
		t = 1, last = A[pnt];
		pnt --;
	}
	relax(last, t);
	ans ++, solve(pnt);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> A[i], cnt[A[i]] ++, st.insert(A[i]);
	for(int i = 1; i <= n; i ++) blk[i] = (A[i] != A[i - 1] ? 0 : blk[i - 1]) + 1;
	solve(n);
	cout << ans << '\n';
	return 0;
}
//! N.N

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 0 / 55