Submission #940696

#	Time	Username	Problem	Language	Result	Execution time	Memory
940696		12345678	Zoltan (COCI16_zoltan)	C++17	140 / 140	375 ms	26964 KiB

zoltan

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5, mod=1e9+7;

int n, v[nx], t, p[nx];
ll ansmx, cnt;
map<int, int> mp;

struct node
{
    int mx, w;
    node(int mx=0, int w=1): mx(mx), w(w) {}
    friend node operator+(const node &a, const node &b) {
        node res;
        res.mx=max(a.mx, b.mx);
        if (a.mx==b.mx) res.w=(a.w+b.w)%mod;
        else res.w=(a.mx>b.mx)?a.w:b.w;
        if (res.mx==0) res.w=1;
        return res;
    }
} dpi[nx], dpd[nx];

struct segtree
{
    node d[4*nx];
    void update(int l, int r, int i, int idx, node vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=d[i]+vl, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    node query(int l, int r, int i, int ql, int qr)
    {
        if (r<ql||qr<l) return node();
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} lis, lds;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    p[0]=1;
    for (int i=1; i<=n; i++) p[i]=(p[i-1]*2)%mod;
    for (int i=1; i<=n; i++) cin>>v[i], mp[v[i]]=0;
    for (auto &[x, y]:mp) y=++t;
    for (int i=n; i>=1; i--)
    {
        node a=lis.query(1, n, 1, mp[v[i]]+1, n);
        node b=lds.query(1, n, 1, 1, mp[v[i]]-1);
        a.mx++;
        b.mx++;
        dpi[i]=a;
        dpd[i]=b;
        lis.update(1, n, 1, mp[v[i]], a);
        lds.update(1, n, 1, mp[v[i]], b);
    }
    for (int i=1; i<=n; i++)
    {
        ll tmp=1, tmx;
        tmx=dpi[i].mx+dpd[i].mx-1;
        tmp=(p[n-tmx]*tmp)%mod;
        tmp=((tmp*dpi[i].w)%mod*dpd[i].w)%mod;
        //cout<<"here "<<i<<' '<<tmp.mx<<' '<<tmp.w<<'\n', cout<<i<<' '<<dpi[i].mx<<' '<<dpi[i].w<<' '<<dpd[i].mx<<' '<<dpd[i].w<<'\n';
        if (tmx>ansmx) ansmx=tmx, cnt=tmp;
        else if (tmx==ansmx) cnt=(cnt+tmp)%mod;
    }
    cout<<ansmx<<' '<<cnt;
    //for (int i=1; i<=n; i++) cout<<i<<' '<<dpi[i].mx<<' '<<dpi[i].w<<' '<<dpd[i].mx<<' '<<dpd[i].w<<'\n';
}

• Subtask 1: 140 / 140