BOJ 25429 노엣지 피자

문제 링크입니다.

$N$은 $l$을 약수로 갖는다

연속한 $l$조각의 맛이 항상 같아야 합니다. 어떤 연속한 $l$조각에서 맨 왼쪽 조각을 떼고 맨 오른쪽 조각의 오른쪽 조각을 붙였을 때 맛이 같으려면, 뗴어낸 조각과 새로 붙인 조각에 올라간 토핑의 맛이 같아야 합니다. 이걸 계속하면, 조각의 번호를 $l$로 나눈 나머지가 같으면 그 위에 올라간 토핑의 맛은 전부 같아야 한다는 결론을 얻을 수 있습니다.

빠르게 관리하기

각 나머지마다 필수로 올려야 하는 토핑들의 리스트를 관리해 줍시다. $N$이 매우 크므로, std::map 과 같은 자료 구조를 이용해 인덱스를 압축한 상태로 관리합시다. 각 나머지 리스트마다, 서로 다른 값의 원소가 둘 이상 있다면 피자를 만들 수 없습니다. 토핑 추가와 삭제를 수행하면서 서로 다른 원소가 몇 개인지를 동시에 관리해 주기 위해서, 각 위치에 어느 토핑이 올라가 있는지, 각 나머지마다 어느 토핑이 몇 개 있는지, 각 나머지마다 서로 다른 토핑이 몇 종류가 있는지를 모두 관리해 주면 됩니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll n, l, q;

map<ll, map<ll, ll>> bucket;
map<ll, ll> bucket_cnt;
map<ll, ll> mp;
int cnt; ll sum;

void erase_topping(ll x){
	bucket[x%l][mp[x]]--;
	if(!bucket[x%l][mp[x]]){
		bucket_cnt[x%l]--;
		if(bucket_cnt[x%l] == 1) cnt--;
		sum -= mp[x];
	}
	mp[x] = 0;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> n >> l >> q;
	while(q--){
		int op; cin >> op;
		if(op == 1){
			ll x, t; cin >> x >> t;
			erase_topping(x);
			mp[x] = t;
			if(!bucket[x%l][t]){
				bucket_cnt[x%l]++;
				if(bucket_cnt[x%l] == 2) cnt++;
				sum += t;
			}
			bucket[x%l][t]++;
		}
		else{
			ll x; cin >> x; erase_topping(x);
		}
		if(!cnt) cout << "YES " << sum << '\n';
		else cout << "NO\n";
	}
}