취미로 코딩하기

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

이번에 볼 문제는 백준 19666번 문제인 Cryptography이다.
문제는 아래 링크를 확인하자.

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

주어진 모든 수 가운데 주어진 순열의 현재 순서의 수보다 "앞서 나올 수 있는" 수의 개수를 빠르게 접근할 수 있다면 이 문제는 어렵지 않게 해결할 수 있을 것이다.

이와 같은 작업은 좌표압축과 세그먼트트리를 이용하여 할 수 있음이 잘 알려져 있지만, pbds(의 rbtree)를 이용하면 (pbds가 무거워서 실행속도는 조금 느리지만) 코드를 빠르게 작성할 수 있다. 이는 코드를 작성하는 속도 대결인 cp에서 유리한 점이라고 생각해 pbds에 익숙해질 겸 pbds로 문제를 해결해보았다.

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

#include <iostream>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename K> using ordered_set = tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

int N;
int A[300000];
ordered_set<int> st;
int fact[300000];
int ans = 1;

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

	cin >> N;
	fact[0] = 1;
	for (int i = 1; i < N; i++) fact[i] = ((ll)fact[i - 1] * i) % 1000000007;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		st.insert(A[i]);
	}

	for (int i = 0; i < N; i++) {
		int ord = st.order_of_key(A[i]);
		ans = ((ll)ord * fact[N - i - 1] + ans) % 1000000007;
		st.erase(A[i]);
	}

	cout << ans;
}