Submission #538207

#	Time	Username	Problem	Language	Result	Execution time	Memory
538207		Cantfindme	Zoltan (COCI16_zoltan)	C++17	14 / 140	127 ms	9712 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 200010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;

int mx;

pi calc(pi a, pi b) {
	if (a.f == b.f) return pi(a.f, (a.s + b.s) % mod);
	else return max(a, b);
}

pi fw1[maxn], fw2[maxn];

int ls(int x) {
	return x & (-x);
}

void upd(pi *fw, int x, pi nv) {
	for (; x <= mx; x+=ls(x)) fw[x] = calc(fw[x], nv);
}

pi sum(pi *fw, int x) {
	pi res = pi(0,0);
	for (; x; x -= ls(x)) res = calc(res, fw[x]);
	return res;
}

int n;
int A[maxn];

int32_t main() {
	FAST
	// ifstream cin("input.txt");

	cin >> n;
	vector <int> v;
	for (int i = 1; i <= n;i++) {
		cin >> A[i];
		v.push_back(A[i]);
	}

	sort(all(v));
	v.resize(unique(v.begin(),v.end()) - v.begin());
	for (int i = 1; i<=n;i++) {
		A[i] = lower_bound(all(v), A[i]) - v.begin() + 1;
	}

	mx = v.size()+1;

	pi rans = pi(0,0);

	for (int i = n; i >= 1; i--) {
		pi aft = sum(fw1, mx - (A[i] + 1));
		pi bef = sum(fw2, A[i] - 1);

		if (aft.s == 0) aft.s = 1;
		aft.f += 1;
		upd(fw1, A[i], aft);

		if (bef.s == 0) bef.s = 1;
		bef.f += 1;
		upd(fw2, mx - A[i], bef);
	
		rans = calc(rans, pi(bef.f + aft.f - 1, bef.s * aft.s));
	}

	for (int i = 0; i < n - rans.f; i++) {
		rans.s *= 2;
		rans.s %= mod;
	}

	cout << rans.f << " " << rans.s << "\n";
}

• Subtask 1: 14 / 140