oj.uz

Submission #846005

# Submission time Handle Problem Language Result Execution time Memory
846005 2023-09-07T05:26:29 Z beaboss Zoltan (COCI16_zoltan) C++14
0 / 140
 153 ms 16740 KB 
// 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

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Incorrect 1 ms 4564 KB Output isn't correct
6 Incorrect 1 ms 4444 KB Output isn't correct
7 Incorrect 1 ms 4568 KB Output isn't correct
8 Incorrect 1 ms 4444 KB Output isn't correct
9 Incorrect 1 ms 4444 KB Output isn't correct
10 Incorrect 1 ms 4440 KB Output isn't correct
11 Incorrect 89 ms 16340 KB Output isn't correct
12 Incorrect 82 ms 15804 KB Output isn't correct
13 Incorrect 68 ms 11372 KB Output isn't correct
14 Incorrect 97 ms 15188 KB Output isn't correct
15 Incorrect 124 ms 16212 KB Output isn't correct
16 Incorrect 153 ms 16740 KB Output isn't correct
17 Incorrect 108 ms 15568 KB Output isn't correct
18 Incorrect 107 ms 15564 KB Output isn't correct
19 Incorrect 118 ms 15748 KB Output isn't correct
20 Incorrect 107 ms 15564 KB Output isn't correct