oj.uz

Submission #874561

# Submission time Handle Problem Language Result Execution time Memory
874561 2023-11-17T09:35:01 Z serifefedartar Zoltan (COCI16_zoltan) C++17
140 / 140
 312 ms 22472 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+7;
const ll LOGN = 20; 
const ll MAXN = 2e5 + 100;

vector<ll> A, cc;
pair<int,ll> sg[4*MAXN];
int index(int k) {
	return upper_bound(cc.begin(), cc.end(), k) - cc.begin();
}

pair<int,ll> merge(pair<int,ll> a, pair<int,ll> b) {
	if (a.f == b.f)
		return {a.f, (a.s + b.s) % MOD};
	return max(a, b);
}

void update(int k, int a, int b, int plc, pair<int,ll> val) {
	if (b < plc || a > plc)
		return ;
	if (a == b) {
		sg[k] = merge(sg[k], val);
		return ;
	}
	update(2*k, a, (a+b)/2, plc, val);
	update(2*k+1, (a+b)/2+1, b, plc, val);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

pair<int,ll> query(int k, int a, int b, int q_l, int q_r) {
	if (b < q_l || a > q_r)
		return {0, 0};
	if (q_l <= a && b <= q_r)
		return sg[k];
	return merge(query(2*k, a, (a+b)/2, q_l, q_r),
					query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}


ll expo(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)
			res = (res * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return res;
}
pair<int,ll> LIS[MAXN], LDS[MAXN];

int main() {
	fast
	int N;
	cin >> N;

	A = vector<ll>(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		cc.push_back(A[i]);
	}
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());

	for (int i = N; i >= 1; i--) {
		pair<int,ll> Q = query(1, 0, N, index(A[i]) + 1, N);
		if (Q.f == 0)
			Q.s++;
		Q.f++;
		LIS[i] = Q;
		update(1, 0, N, index(A[i]), Q);
	}
	for (int i = 0; i < 4*MAXN; i++)
		sg[i] = {0, 0};
	for (int i = N; i >= 1; i--) {
		pair<int,ll> Q = query(1, 0, N, 0, index(A[i]) - 1);
		if (Q.f == 0)
			Q.s++;
		Q.f++;
		LDS[i] = Q;
		update(1, 0, N, index(A[i]), LDS[i]);
	}

	pair<int,ll> ans = {0, 0};
	for (int i = 1; i <= N; i++) {
		pair<int,ll> now = {0, 0};
		now = {LIS[i].f + LDS[i].f - 1, ((LIS[i].s * LDS[i].s % MOD) * expo(2, N - LIS[i].f - LDS[i].f + 1)) % MOD};
		ans = merge(ans, now);
	}
	cout << ans.f << " " << ans.s << "\n";
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14884 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 182 ms 21016 KB Output is correct
12 Correct 157 ms 20304 KB Output is correct
13 Correct 149 ms 20372 KB Output is correct
14 Correct 195 ms 20424 KB Output is correct
15 Correct 266 ms 21428 KB Output is correct
16 Correct 312 ms 22312 KB Output is correct
17 Correct 255 ms 22344 KB Output is correct
18 Correct 229 ms 22468 KB Output is correct
19 Correct 221 ms 22472 KB Output is correct
20 Correct 234 ms 22472 KB Output is correct