Submission #383288

#	Time	Username	Problem	Language	Result	Execution time	Memory
383288		peijar	Zoltan (COCI16_zoltan)	C++17	140 / 140	151 ms	14880 KiB

zoltan

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MOD = 1e9 + 7;

pair<int,int> fusion(pair<int, int> lhs, pair<int, int> rhs)
{
	auto [ml, cl] = lhs;
	auto [mr, cr] = rhs;
	if (mr > ml) return rhs;
	if (ml > mr) return lhs;
	return make_pair(ml, (cl + cr) % MOD);
}

int fastpow(int a, int b)
{
	if (!b) return 1;
	int ret = fastpow(a, b/2);
	return (b & 1 ? a : 1) * ret % MOD* ret % MOD;
}

struct Fenwick
{
	int N;
	vector<pair<int, int>> bit;

	Fenwick(int n) : N(n+1), bit(N) {}

	void upd(int iPos, pair<int, int> val)
	{
		for (iPos++; iPos < N; iPos += iPos & -iPos)
			bit[iPos] = fusion(val, bit[iPos]);
	}

	pair<int, int> query(int r) // < r
	{
		pair<int, int> sol(0,0);
		for (; r; r -= r & -r)
			sol = fusion(bit[r], sol);
		return sol;
	}
};

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbElem;
	cin >> nbElem;
	vector<int> arr(nbElem);
	vector<int> vals;
	for (auto &v : arr)
	{
		cin >> v; vals.push_back(v);
	}
	sort(vals.begin(), vals.end());
	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
	for (int iEl = 0; iEl < nbElem; ++iEl) 
		arr[iEl] = 1 + lower_bound(vals.begin(), vals.end(), arr[iEl]) - vals.begin();
	
	int nbDiff = vals.size() + 1;
	Fenwick increasingDp(nbDiff);
	increasingDp.upd(0, make_pair(0, 1));
	for (int iEl(nbElem-1); iEl >= 0; --iEl)
	{
		pair<int, int> q = increasingDp.query(arr[iEl]);
		q.first++;
		increasingDp.upd(arr[iEl], q);
	}

	Fenwick decreasingDp(nbDiff);
	decreasingDp.upd(0, make_pair(0, 1));
	vector<pair<int, int>> bestDecreasing(nbDiff+1);
	bestDecreasing[nbDiff] = make_pair(0, 1);
	for (int iEl(nbElem-1); iEl >= 0; --iEl)
	{
		pair<int, int> q = decreasingDp.query(nbDiff - arr[iEl]);
		q.first++;
		bestDecreasing[arr[iEl]] = fusion(bestDecreasing[arr[iEl]], q);
		decreasingDp.upd(nbDiff - arr[iEl], q);
	}
	pair<int, int> sol(0, 0);
	for (int lastDec(0); lastDec <= nbDiff; ++lastDec)
	{
		pair<int, int> q = increasingDp.query(lastDec);
		q.first += bestDecreasing[lastDec].first;
		q.second *= bestDecreasing[lastDec].second;
		q.second %= MOD;
		sol = fusion(sol, q);
	}
	sol.second *= fastpow(2, nbElem-sol.first);
	sol.second %= MOD;
	sol.second *= fastpow(2, MOD-2);
	sol.second %= MOD;
	cout << sol.first << ' ' << sol.second << endl;
}

• Subtask 1: 140 / 140