Submission #383288

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
383288	2021-03-29T12:43:56 Z	peijar	Zoltan (COCI16_zoltan)	C++17	140 / 140	151 ms	14880 KB

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.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	2 ms	364 KB	Output is correct
11	Correct	79 ms	11620 KB	Output is correct
12	Correct	70 ms	10084 KB	Output is correct
13	Correct	63 ms	9576 KB	Output is correct
14	Correct	94 ms	10468 KB	Output is correct
15	Correct	126 ms	12900 KB	Output is correct
16	Correct	151 ms	14880 KB	Output is correct
17	Correct	95 ms	12812 KB	Output is correct
18	Correct	101 ms	12680 KB	Output is correct
19	Correct	94 ms	12772 KB	Output is correct
20	Correct	93 ms	12772 KB	Output is correct