oj.uz

답안 #874507

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874507 2023-11-17T07:23:35 Z serifefedartar Zoltan (COCI16_zoltan) C++17
14 / 140
 273 ms 41244 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20; 
const ll MAXN = 2e5 + 100;
#define int long long

vector<pair<int,int>> v;
vector<int> arr, cc;
pair<int,int> sg[4*MAXN], w1[MAXN], w2[MAXN];
pair<int,int> merge(pair<int,int> a, pair<int,int> b) {
	if (a.f == b.f)
		return {a.f, (a.s + b.s) % MOD};
	return max(a, b);
}

void update(int k, int a, int b, int plc, pair<int,int> val) {
	if (b < plc || a > plc)
		return ;
	if (a == b) {
		sg[k] = merge(val, sg[k]);
		return ;
	}
	update(2*k, a, (a+b)/2, plc, val);
	update(2*k+1, (a+b)/2+1, b, plc, val);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

pair<int,int> query(int k, int a, int b, int q_l, int q_r) {
	if (b < q_l || a > q_r)
		return {0, 0};
	if (q_l <= a && b <= q_r)
		return sg[k];
	return merge(query(2*k, a, (a+b)/2, q_l, q_r),
				query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}

int index(int k) {
	return upper_bound(cc.begin(), cc.end(), k) - cc.begin();
}

map<int,int> cnt;
signed main() {
	fast
	int N;
	cin >> N;

	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		cc.push_back(A[i]);
		cnt[A[i]]++;
	}
	for (int i = 0; i < N; i++)
		v.push_back({A[i], i+1});
	sort(v.begin(), v.end(), [&](pair<int,int> a, pair<int,int> b) {
		return make_pair(a.f, -a.s) < make_pair(b.f, -b.s); 
	});
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end()); 

	for (auto u : v)
		arr.push_back(u.s);

	for (int i = 0; i < N; i++) {
		pair<int,int> Q = query(1, 0, N, index(arr[i]) + 1, N);
		if (Q.f == 0)
			Q.s++;
		w1[i+1] = {Q.f + 1, Q.s};
		update(1, 0, N, index(arr[i]), w1[i+1]);
	}
	for (int i = 0; i < 4*MAXN; i++)
		sg[i] = {0, 0};

	for (int i = N-1; i >= 0; i--) {
		pair<int,int> Q = query(1, 0, N, index(arr[i]) + 1, N);
		if (Q.f == 0)
			Q.s++;
		w2[i+1] = {Q.f + 1, Q.s};
		update(1, 0, N, index(arr[i]), w2[i+1]); 
	}

	pair<int,int> ans = {0, 0};
	for (int i = 1; i <= N; i++)
		ans = merge(ans, {w1[i].f + w2[i].f - 1, (w1[i].s * w2[i].s) % MOD});

	for (auto u : cnt)
		ans.s = (ans.s * u.s) % MOD; 
	cout << ans.f << " " << ans.s << "\n";
}

Subtask #1
14.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 14940 KB Output isn't correct
2 Incorrect 2 ms 14940 KB Output isn't correct
3 Incorrect 2 ms 14940 KB Output isn't correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Incorrect 2 ms 14940 KB Output isn't correct
7 Incorrect 3 ms 14940 KB Output isn't correct
8 Incorrect 3 ms 14936 KB Output isn't correct
9 Incorrect 3 ms 14940 KB Output isn't correct
10 Incorrect 3 ms 14940 KB Output isn't correct
11 Runtime error 173 ms 38388 KB Memory limit exceeded
12 Runtime error 153 ms 35132 KB Memory limit exceeded
13 Incorrect 137 ms 32092 KB Output isn't correct
14 Runtime error 162 ms 35680 KB Memory limit exceeded
15 Runtime error 209 ms 38368 KB Memory limit exceeded
16 Runtime error 242 ms 41244 KB Memory limit exceeded
17 Runtime error 264 ms 39736 KB Memory limit exceeded
18 Runtime error 271 ms 40476 KB Memory limit exceeded
19 Runtime error 260 ms 39452 KB Memory limit exceeded
20 Runtime error 273 ms 39700 KB Memory limit exceeded