Submission #1108885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108885		vjudge1	Zoltan (COCI16_zoltan)	C++17	42 / 140	397 ms	29636 KiB

zoltan

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int mod=1e9+7;
pii dp[400005][2], st[2][800005], p1, p2;
vector<int> b;
map<int, int> id;
int sz, a[400005], two[200005];

pii Merge(pii x, pii y)
{
    if (x.first>y.first) {return x;}
    else if (y.first>x.first) {return y;}
    else {return {x.first, (x.second+y.second)%mod};};
};

void update(int idx, int x, int l, int r, int pos, pii p)
{
    if (l>r || l>pos || r<pos) {return;}
    else if (l==r) {st[idx][x]=Merge(st[idx][x], p);}
    else
    {
        update(idx, x*2+1, l, (l+r)/2, pos, p);
        update(idx, x*2+2, (l+r)/2+1, r, pos, p);
        st[idx][x]=Merge(st[idx][x*2+1], st[idx][x*2+2]);
    };
}

pii getmax(int idx, int x, int l, int r, int pos1, int pos2)
{
    if (l>r || l>pos2 || r<pos1) {return {0LL, 0LL};}
    else if (pos1<=l && r<=pos2) {return st[idx][x];}
    else
    {
        return Merge(getmax(idx, x*2+1, l, (l+r)/2, pos1, pos2), getmax(idx, x*2+2, (l+r)/2+1, r, pos1, pos2));
    };
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
	int n, i;
	cin >> n;
	two[0]=1;
	for (i=1; i<=n; i++) {two[i]=two[i-1]*2%mod;};
	for (i=1; i<=n; i++)
    {
        cin >> a[i];
        b.push_back(a[i]);
    };
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    sz=b.size();
    for (i=0; i<sz; i++) {id[b[i]]=i+1;};
    reverse(a+1, a+n+1);
    for (i=1; i<=n; i++) {a[i]=id[a[i]];};
    for (i=n+1; i<=2*n; i++) {a[i]=a[2*n-i+1];};
    for (i=1; i<n; i++)
    {
        dp[i][0]=getmax(0, 0, 1, sz, 1, a[i]-1);
        dp[i][0].first++;
        if (dp[i][0].first==1) {dp[i][0].second=1;};
        update(0, 0, 1, sz, a[i], dp[i][0]);
    };
    dp[n][1]=dp[n+1][1]=getmax(0, 0, 1, sz, 1, a[n]-1);
    dp[n][1].first++; dp[n+1][1].first++;
    if (dp[n][1].first==1) {dp[n][1].second=1;};
    if (dp[n+1][1].first==1) {dp[n+1][1].second=1;};
    update(1, 0, 1, sz, a[n], dp[n][1]);
    for (i=n+2; i<=2*n; i++)
    {
        dp[i][0]=getmax(0, 0, 1, sz, 1, a[i]-1);
        dp[i][0].first++;
        if (dp[i][0].first==1) {dp[i][0].second=1;};
        update(0, 0, 1, sz, a[i], dp[i][0]);
        dp[i][1]=getmax(1, 0, 1, sz, 1, a[i]-1);
        if (dp[i][1].first>0) {dp[i][1].first++;};
        update(1, 0, 1, sz, a[i], dp[i][1]);
    };
    p1=getmax(0, 0, 1, sz, 1, sz);
    p2=getmax(1, 0, 1, sz, 1, sz);
    if (p1.first>p2.first) {cout << p1.first << " " << p1.second*two[n-p1.first-1]%mod;}
    else if (p1.first<p2.first) {cout << p2.first << " " << p2.second*two[n-p2.first]%mod;}
    else {cout << p1.first << " " << ((p1.second*two[n-p1.first-1])%mod+(p2.second*two[n-p1.first])%mod)%mod;};
}

• Subtask 1: 42 / 140