Submission #846005

#	Time	Username	Problem	Language	Result	Execution time	Memory
846005		beaboss	Zoltan (COCI16_zoltan)	C++14	0 / 140	153 ms	16740 KiB

zoltan

// Source: https://oj.uz/problem/view/COCI16_zoltan
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

const ll N = 2e5 + 10;
const ll MOD = 1e9+7;
#define lc i << 1
#define rc (i << 1) + 1

ll binpow(ll x, ll n) {
	assert(n >= 0);
	x %= MOD;  // note: m * m must be less than 2^63 to avoid ll overflow
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % MOD; }
		x = x * x % MOD;
		n /= 2;
	}
	return res;
}

ll n;

pii st[4 * N]; // max and number of maximums

pii comb(pii a, pii b) { // MODIFY COMBINER FUNCTION
	if (a.f == b.f) return {a.f, b.s + a.s % MOD};
	else return max(a, b);
}

void up(ll i) {
	st[i] = comb(st[lc], st[rc]);
}

void update(ll ind, pii val, ll i = 1, ll l = 0, ll r = n) { // update pos ind with value val
	if (l >= r) return;
	if (r - l == 1) {

		st[i] = comb(st[i], val);
		// cout << val.f << val.s << st[i].f << st[i].s << endl;
		return;
	}

	ll m = (l + r)/2;

	if (m > ind) update(ind, val, lc, l, m); // contained in left child
	else update(ind, val, rc, m, r); // contained in right child

	up(i); // update current index
}

pii query(ll ql, ll qr, ll i = 1, ll l = 0, ll r = n) { // query from [ql, qr)
	
	if (l >= r) return {0, 0}; // identity
	if (ql <= l && qr >= r) { // fully contained
		return st[i];
	}

	if (r - l == 1) return {0, 0}; // leaf node

	ll m = (l + r)/2;

	pii acc = {0, 1}; // SET DEFAULT VALUE

	if (m >= ql) acc = comb(query(ql, qr, lc, l, m), acc);
	if (m <= qr) acc = comb(acc, query(ql, qr, rc, m, r));

	return acc;
}


ll a[N];

ll decr[N];
ll inc[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// ll n;
	cin >> n;

	vi alt(n);

	FOR(i, 0, n) {
		cin >> a[i];
		alt[i]=a[i];
	}

	sort(alt.begin(), alt.end());
	alt.resize(unique(alt.begin(), alt.end())-alt.begin());

	FOR(i, 0, n) a[i] = lower_bound(alt.begin(), alt.end(), a[i]) - alt.begin();

	vi seq; // longest decrreasing sequence

	for (ll i = n-1; i >= 0; i--) {
		auto lb = lower_bound(seq.begin(), seq.end(), a[i])-seq.begin();

		if (lb == seq.size()) {
			seq.pb(a[i]);
			decr[i]=seq.size();
		} else {
			decr[i]=lb+1;
			seq[lb]=a[i];
		}
		// cout << a[i] << decr[i] << endl;

	}

	// cout << endl;

	seq.clear();

	pii ans = {0, 0};

	for (ll i = n-1; i >= 0; i--) {
		auto lb = lower_bound(seq.begin(), seq.end(), -a[i])-seq.begin();

		if (lb == seq.size()) {
			seq.pb(-a[i]);
			inc[i]=seq.size();
		} else {
			inc[i]=lb+1;
			seq[lb]=-a[i];
		}

		pii q = query(0, a[i]);
		// cout << a[i] << inc[i] << q.f << q.s << endl;
		ans = comb(ans, {q.f + inc[i], q.s});

		update(a[i], {decr[i], 1}); // start of increasing is more than start of decreasing and increasing starts before decreasing


	}

	cout << ans.f << ' ' << (ans.s * binpow(2, n-ans.f)) % MOD << endl;

	




	



}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:117:10: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |   if (lb == seq.size()) {
      |       ~~~^~~~~~~~~~~~~
zoltan.cpp:137:10: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   if (lb == seq.size()) {
      |       ~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 140