oj.uz

Submission #940691

# Submission time Handle Problem Language Result Execution time Memory
940691 2024-03-07T13:29:17 Z 12345678 Zoltan (COCI16_zoltan) C++17
0 / 140
 442 ms 49200 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

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

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

struct node
{
    ll mx, w;
    node(ll mx=0, ll 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;
    }
} ans, 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++)
    {
        node tmp;
        tmp.mx=dpi[i].mx+dpd[i].mx-1;
        tmp.w=(p[n-tmp.mx]*tmp.w)%mod;
        tmp.w=((tmp.w*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';
        ans=ans+tmp;
    }
    cout<<ans.mx<<' '<<ans.w;
    //for (int i=1; i<=n; i++) cout<<i<<' '<<dpi[i].mx<<' '<<dpi[i].w<<' '<<dpd[i].mx<<' '<<dpd[i].w<<'\n';
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 33372 KB Memory limit exceeded
2 Runtime error 6 ms 33452 KB Memory limit exceeded
3 Runtime error 6 ms 33372 KB Memory limit exceeded
4 Runtime error 5 ms 33372 KB Memory limit exceeded
5 Runtime error 5 ms 33372 KB Memory limit exceeded
6 Runtime error 5 ms 33372 KB Memory limit exceeded
7 Runtime error 8 ms 33784 KB Memory limit exceeded
8 Runtime error 6 ms 33372 KB Memory limit exceeded
9 Runtime error 6 ms 33372 KB Memory limit exceeded
10 Runtime error 7 ms 33372 KB Memory limit exceeded
11 Runtime error 249 ms 45656 KB Memory limit exceeded
12 Runtime error 218 ms 44020 KB Memory limit exceeded
13 Runtime error 202 ms 43356 KB Memory limit exceeded
14 Runtime error 306 ms 44112 KB Memory limit exceeded
15 Runtime error 370 ms 47052 KB Memory limit exceeded
16 Runtime error 442 ms 49200 KB Memory limit exceeded
17 Runtime error 288 ms 46620 KB Memory limit exceeded
18 Runtime error 262 ms 46600 KB Memory limit exceeded
19 Runtime error 283 ms 46620 KB Memory limit exceeded
20 Runtime error 267 ms 46504 KB Memory limit exceeded