Submission #815978

#	Time	Username	Problem	Language	Result	Execution time	Memory
815978		acatmeowmeow	Zoltan (COCI16_zoltan)	C++11	140 / 140	143 ms	16256 KiB

zoltan

#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 2e5, modulo = 1e9 + 7;
int n, x[N + 5], y[N + 5];
pair<int, int> dp[N + 5], dp2[N + 5], tree[N + 5];
vector<int> mp;

pair<int, int> combine(pair<int, int>&a, pair<int, int>&b) {
	if (a.first == b.first) return {a.first, (a.second + b.second) % modulo}; 
	else return a > b ? a : b;
}
void update(int k, pair<int, int>x) {
	for (; k <= n; k += k&-k) tree[k] = combine(tree[k], x);
}

pair<int, int> query(int k) {
	pair<int, int> ans = {0, 0};
	for (; k; k -= k&-k) ans = combine(ans, tree[k]);
	return ans;
}

int binpow(int n, int k) {
	if (!k) return 1;
	else {
		int ans = binpow(n, k/2);
		ans *= ans, ans %= modulo;
		if (k & 1) ans *= n, ans %= modulo;
		return ans;
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> x[i];
	for (int i = 1; i <= n; i++) mp.push_back(-x[i]);
	sort(mp.begin(), mp.end());
	mp.erase(unique(mp.begin(), mp.end()), mp.end());
	auto getIndex = [&](int p) { return lower_bound(mp.begin(), mp.end(), p) - mp.begin() + 1; };
	for (int i = 1; i <= n; i++) y[i] = getIndex(-x[i]);
	for (int i = n; i >= 1; i--) {
		pair<int, int> res = query(y[i] - 1);
		if (!res.first) dp[i] = {1, 1};
		else dp[i] = {res.first + 1, res.second};
		update(y[i], dp[i]);
	}
	
	mp.clear();
	for (int i = 1; i <= n; i++) tree[i] = {0, 0};
	for (int i = 1; i <= n; i++) mp.push_back(x[i]);
	sort(mp.begin(), mp.end());
	mp.erase(unique(mp.begin(), mp.end()), mp.end());
	for (int i = n; i >= 1; i--) {
		y[i] = getIndex(x[i]);
		pair<int, int> res = query(y[i] - 1);
		if (!res.first) dp2[i] = {1, 1};
		else dp2[i] = {res.first + 1, res.second};
		update(y[i], dp2[i]);
	}
	
	int ans = 0, total = 0;
	for (int i = 1; i <= n; i++) {
		if (dp[i].first + dp2[i].first - 1 > ans) {
			ans = dp[i].first + dp2[i].first - 1;
			total = dp[i].second*dp2[i].second, total %= modulo;
		} else if (dp[i].first + dp2[i].first - 1 == ans) {
			total += dp[i].second*dp2[i].second, total %= modulo;
		}
	}
	total *= binpow(2, n - ans), total %= modulo;
	cout << ans << " " << total << '\n';
	return 0;
}

• Subtask 1: 140 / 140