제출 #1238505

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238505		pvb.tunglam	Zoltan (COCI16_zoltan)	C++20	140 / 140	64 ms	9800 KiB

zoltan

#include <bits/stdc++.h>
#define hash _hash_ 
#define y1 _y1_
#define left _left_ 
#define right _right_
#define dec _dec_   	
using namespace std;

using ll = long long;
using ull = unsigned long long;

	/*----------- I alone decide my fate! ------------*/
/*  I just do what I gotta, in the heat of the summer...  */

const ll MOD = 1e9 + 7;
int N, a[200009], bit[200009], lis[200009], lds[200009];
pair <int, int> nen[200009];
ll numWay[200009], numLis[200009], numLds[200009];

ll powder(ll a, ll b) {
	if (b == 0) return 1;
	ll half = powder(a, b/2);
	if (b & 1) {
		return ((half * half) % MOD) * a % MOD; 
	}
	else return (half * half) % MOD;
}

void update1(int x, int val, ll way) {
	while (x <= N) {
		if (val > bit[x]) {
			bit[x] = max(bit[x], val);
			numWay[x] = way;
		}
		else if (val == bit[x]) {
			numWay[x] = (numWay[x] + way) % MOD;
		}
		x += x &- x;
	}
}

pair <int, ll> get1(int x) {
	pair <int, ll > ret = {0, 0};
	while (x) {
		if (bit[x] > ret.first) {
			ret.first = bit[x];
			ret.second = numWay[x];
		}
		else if (bit[x] == ret.first) {
			ret.second = (ret.second + numWay[x]) % MOD;
		}
		x -= x &- x;
	}
	return ret;
}

void update2(int x, int val, ll way) {
	while (x) {
		if (val > bit[x]) {
			bit[x] = max(bit[x], val);
			numWay[x] = way;
		}
		else if (val == bit[x]) {
			numWay[x] = (numWay[x] + way) % MOD;
		}
		x -= x &- x;
	}
}

pair <int, ll> get2(int x) {
	pair <int, ll > ret = {0, 0};
	while (x <= N) {
		if (bit[x] > ret.first) {
			ret.first = bit[x];
			ret.second = numWay[x];
		}
		else if (bit[x] == ret.first) {
			ret.second = (ret.second + numWay[x]) % MOD;
		}
		x += x &- x;
	}
	return ret;
}

void solve() {
	cin >> N;
	for (int i = 1; i <= N; i ++) {
		cin >> a[i];
		nen[i] = {a[i], i};
	}
	sort(nen + 1, nen + N + 1);
	int dem = 0;
	for (int i = 1; i <= N; i ++) {
		if (i == 1 || nen[i].first != nen[i - 1].first) dem ++;
		a[nen[i].second] = dem;
	}
	for (int i = N; i >= 1; i --) {
		pair <int, ll> val = get1(a[i] - 1);
		ll num = val.second;
		if (num == 0) num ++;
		int j = val.first + 1;
		lis[i] = j; 
		numLis[i] = num;
		update1(a[i], j, num);
	}
	for (int i = 1; i <= N; i ++) bit[i] = numWay[i] = 0;
	for (int i = N; i >= 1; i --) {
		pair <int, ll> val = get2(a[i] + 1);
		ll num = val.second;
		if (num == 0) num ++;
		int j = val.first + 1;
		lds[i] = j; 
		numLds[i] = num;
		update2(a[i], j, num);
	}
	int maxLen = 0;
	ll res = 0;
	for (int i = 1; i <= N; i ++) {
		maxLen = max(maxLen, lis[i] + lds[i] - 1);
	}
	for (int i = 1; i <= N; i ++) {
		if (lis[i] + lds[i] - 1 == maxLen) {
			res = (res + numLds[i] % MOD * numLis[i]) % MOD;
		}
	}
	res = (res * powder(2, N - maxLen)) % MOD;
	cout << maxLen << " " << res;
}



signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	solve();
}


/*
  How can you see into my eyes, like open doors?
  Leading you down into my core, where I've become so numb
  Without a soul, my spirit's sleeping somewhere cold
  Until you find it here and bring it back home!
  Wake me up! Wake me up inside
  Cant wake up? Wake me up inside
*/

• Subtask 1: 140 / 140