Submission #874504

#	Time	Username	Problem	Language	Result	Execution time	Memory
874504		serifefedartar	Zoltan (COCI16_zoltan)	C++17	14 / 140	279 ms	41532 KiB

zoltan

#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};
	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());
	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 / 140