제출 #874554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874554		serifefedartar	Zoltan (COCI16_zoltan)	C++17	21 / 140	255 ms	9932 KiB

zoltan

#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;
int sg[4*MAXN];
int index(int k) {
	return upper_bound(cc.begin(), cc.end(), k) - cc.begin();
}

void update(int k, int a, int b, int plc, int val) {
	if (b < plc || a > plc)
		return ;
	if (a == b) {
		sg[k] = max(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] = max(sg[2*k], sg[2*k+1]);
}

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

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);
}

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;
}
int 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--) {
		int Q = query(1, 0, N, index(A[i]) + 1, N);
		LIS[i] = Q + 1;
		update(1, 0, N, index(A[i]), LIS[i]);
	}
	for (int i = 0; i < 4*MAXN; i++)
		sg[i] = 0;
	for (int i = N; i >= 1; i--) {
		int Q = query(1, 0, N, 0, index(A[i]) - 1);
		LDS[i] = Q + 1;
		update(1, 0, N, index(A[i]), LDS[i]);
	}

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

• Subtask 1: 21 / 140