oj.uz

답안 #874559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874559 2023-11-17T09:15:39 Z serifefedartar Zoltan (COCI16_zoltan) C++17
84 / 140
 306 ms 23464 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 * expo(2, N - LIS[i].f - LDS[i].f + 1)};
		ans = merge(ans, now);
	}
	cout << ans.f << " " << ans.s << "\n";
}

Subtask #1
84.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14936 KB Output is correct
2 Correct 2 ms 15192 KB Output is correct
3 Correct 2 ms 15048 KB Output is correct
4 Correct 2 ms 14940 KB Output is correct
5 Correct 2 ms 14940 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 14936 KB Output is correct
9 Incorrect 3 ms 14940 KB Output isn't correct
10 Incorrect 4 ms 14928 KB Output isn't correct
11 Incorrect 180 ms 21800 KB Output isn't correct
12 Incorrect 155 ms 21164 KB Output isn't correct
13 Incorrect 150 ms 21064 KB Output isn't correct
14 Incorrect 192 ms 21456 KB Output isn't correct
15 Incorrect 257 ms 22728 KB Output isn't correct
16 Incorrect 306 ms 23464 KB Output isn't correct
17 Correct 246 ms 23208 KB Output is correct
18 Correct 221 ms 23116 KB Output is correct
19 Correct 220 ms 23240 KB Output is correct
20 Correct 224 ms 23236 KB Output is correct