oj.uz

답안 #874554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874554 2023-11-17T08:57:56 Z serifefedartar Zoltan (COCI16_zoltan) C++17
21 / 140
 255 ms 9932 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;
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.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 3416 KB Output isn't correct
2 Incorrect 1 ms 3416 KB Output isn't correct
3 Incorrect 1 ms 3420 KB Output isn't correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Incorrect 2 ms 3420 KB Output isn't correct
8 Incorrect 2 ms 3420 KB Output isn't correct
9 Incorrect 2 ms 3420 KB Output isn't correct
10 Incorrect 2 ms 3420 KB Output isn't correct
11 Incorrect 165 ms 8568 KB Output isn't correct
12 Incorrect 140 ms 7924 KB Output isn't correct
13 Incorrect 131 ms 7628 KB Output isn't correct
14 Incorrect 180 ms 8460 KB Output isn't correct
15 Incorrect 221 ms 9164 KB Output isn't correct
16 Incorrect 255 ms 9932 KB Output isn't correct
17 Incorrect 208 ms 9436 KB Output isn't correct
18 Incorrect 198 ms 9488 KB Output isn't correct
19 Incorrect 201 ms 9636 KB Output isn't correct
20 Incorrect 200 ms 9792 KB Output isn't correct