[BOJ 11735 // C++] 정산소

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11735번 문제인 정산소이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/11735 

11735번: 정산소

총 N개의 행이 있는 사각형에서 K번 행에 적혀있는 수들의 합은 다음과 같이 나타낼 수 있다.

(1~N의합 - (사라진 열의 번호들의 합)) + (K*(남아있는 열의 개수))

 

사라진 열의 번호들의 합과 남아있는 열의 개수는 쿼리 하나당 O(1)에 갱신이 가능하다.

 

K번 열에 적혀있는 수들의 합도 마찬가지 방식으로 계산해낼 수 있다.

 

답이 32비트 정수 자료형으로 담을 수 없는 큰 값이 나올 수 있으므로 64비트 자료형을 이용하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll N, Q;
ll rCnt, cCnt;
ll rSum, cSum;
bool delR[1000001], delC[1000001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> Q;
	rCnt = cCnt = N;
	rSum = cSum = N * (N + 1) / 2;

	while (Q--) {
		char c; ll x; cin >> c >> x;
		if (c == 'R') {
			if (delR[x]) {
				cout << 0 << '\n';
				continue;
			}
			cout << rSum + rCnt * x << '\n';
			delR[x] = 1;
			cSum -= x;
			cCnt--;
		}
		else {
			if (delC[x]) {
				cout << 0 << '\n';
				continue;
			}
			cout << cSum + cCnt * x << '\n';
			delC[x] = 1;
			rSum -= x;
			rCnt--;
		}
	}
}