oj.uz

답안 #442128

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442128 2021-07-07T07:47:18 Z Nima_Naderi Money (IZhO17_money) C++14
0 / 100
 0 ms 332 KB 
//In the name of GOD
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e6 + 10;
ll n, ans;
ll A[MXN], cnt[MXN], blk[MXN];
unordered_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
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -