Submission #443728

#	Time	Username	Problem	Language	Result	Execution time	Memory
443728		penguinhacker	Zoltan (COCI16_zoltan)	C++14	112 / 140	308 ms	10992 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5, M=1e9+7;
int n, a[mxN];
ar<int, 2> ic[mxN], dc[mxN], st[1<<19];
vector<int> d;

ar<int, 2> inc(ar<int, 2> x) {
	++x[0];
	return x;
}

ar<int, 2> cmb(ar<int, 2> x, ar<int, 2> y) {
	return x[0]^y[0]?max(x, y):ar<int, 2>{x[0], (x[1]+y[1])%M};
}

void upd(int i, ar<int, 2> x, int u=1, int l=0, int r=d.size()-1) {
	if (l==r) {
		st[u]=cmb(st[u], x);
		return;
	}
	int mid=(l+r)/2;
	i<=mid?upd(i, x, 2*u, l, mid):upd(i, x, 2*u+1, mid+1, r);
	st[u]=cmb(st[2*u], st[2*u+1]);
}

ar<int, 2> qry(int ql, int qr, int u=1, int l=0, int r=d.size()-1) {
	if (l>qr||r<ql)
		return {0, 0};
	if (ql<=l&&r<=qr)
		return st[u];
	int mid=(l+r)/2;
	return cmb(qry(ql, qr, 2*u, l, mid), qry(ql, qr, 2*u+1, mid+1, r));
}

void psh(ar<int, 2> t[], int u=1, int l=0, int r=d.size()-1) {
	if (l==r) {
		t[l]=st[u];
		st[u]={};
		return;
	}
	st[u]={};
	int mid=(l+r)/2;
	psh(t, 2*u, l, mid);
	psh(t, 2*u+1, mid+1, r);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i)
		cin >> a[i];
	d=vector<int>(a, a+n);
	sort(d.begin(), d.end());
	d.resize(unique(d.begin(), d.end())-d.begin());
	for (int i=n-1; ~i; --i) {
		a[i]=lower_bound(d.begin(), d.end(), a[i])-d.begin();
		upd(a[i], cmb(inc(qry(a[i]+1, d.size()-1)), {1, 1}));
	}
	psh(ic);
	for (int i=n-1; ~i; --i)
		upd(a[i], cmb(inc(qry(0, a[i]-1)), {1, 1}));
	psh(dc);
	for (int i=(int)d.size()-2; ~i; --i)
		ic[i]=cmb(ic[i], ic[i+1]);
	int l=ic[0][0];
	for (int i=0; i<d.size(); ++i) {
		l=max(l, dc[i][0]);
		if (i+1<d.size())
			l=max(l, dc[i][0]+ic[i+1][0]);
	}
	ll ans=ic[0][0]==l?ic[0][1]:0;
	for (int i=0; i<d.size(); ++i) {
		if (dc[i][0]==l)
			ans=(ans+dc[i][1])%M;
		if (i+1<d.size()&&dc[i][0]+ic[i+1][0]==l)
			ans=(ans+dc[i][1]*ic[i+1][1])%M;
	}
	for (int i=0; i<n-l; ++i)
		ans=ans*2%M;
	ans=ans*(M+1)/2%M;
	cout << l << " " << ans;
	return 0;
}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i=0; i<d.size(); ++i) {
      |                ~^~~~~~~~~
zoltan.cpp:74:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   if (i+1<d.size())
      |       ~~~^~~~~~~~~
zoltan.cpp:78:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i=0; i<d.size(); ++i) {
      |                ~^~~~~~~~~
zoltan.cpp:81:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   if (i+1<d.size()&&dc[i][0]+ic[i+1][0]==l)
      |       ~~~^~~~~~~~~

• Subtask 1: 112 / 140