oj.uz

Submission #940696

# Submission time Handle Problem Language Result Execution time Memory
940696 2024-03-07T13:33:36 Z 12345678 Zoltan (COCI16_zoltan) C++17
140 / 140
 375 ms 26964 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16988 KB Output is correct
2 Correct 3 ms 16832 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 17240 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 17152 KB Output is correct
7 Correct 5 ms 17088 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 5 ms 16988 KB Output is correct
11 Correct 230 ms 24916 KB Output is correct
12 Correct 188 ms 23636 KB Output is correct
13 Correct 175 ms 23332 KB Output is correct
14 Correct 235 ms 23976 KB Output is correct
15 Correct 314 ms 25428 KB Output is correct
16 Correct 375 ms 26964 KB Output is correct
17 Correct 258 ms 25524 KB Output is correct
18 Correct 263 ms 25504 KB Output is correct
19 Correct 250 ms 25680 KB Output is correct
20 Correct 234 ms 25428 KB Output is correct