Submission #1216331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216331		DangKhoizzzz	Zoltan (COCI16_zoltan)	C++20	91 / 140	228 ms	29420 KiB

zoltan

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;


pii merging(pii a, pii b)
{
    if(a.fi == b.fi) return {a.fi, (a.se + b.se)%mod};
    else return max(a, b);
}

struct Segment_Tree
{
    pii st[maxn*4];
    void update(int id, int l, int r, int pos, pii val)
    {
        if(r < pos || l > pos) return;
        if(l == r)
        {
            st[id] = merging(val , st[id]);
            return;
        }
        int mid = (l+r) >> 1;
        update(id*2, l, mid, pos, val);
        update(id*2+1, mid+1, r, pos, val);
        st[id] = merging(st[id*2], st[id*2+1]);
    }
    pii get(int id, int l, int r, int u, int v)
    {
        if(r < u || l > v) return {-INF, 0};
        if(u <= l && r <= v) return st[id];
        int mid = (l+r) >> 1;
        return merging(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
    }
} ST[2];

int n , a[maxn] , pow_2[maxn];
pii res_do[maxn] , res_up[maxn] , suf[maxn] , ans = {0 , 0};

void compress()
{
    vector <int> val;
    for(int i = 1; i <= n; i++) val.push_back(a[i]);
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    for(int i = 1; i <= n; i++)
    {
        a[i] = upper_bound(val.begin(), val.end(), a[i]) - val.begin();
    }
}

void solve()
{
    pow_2[0] = 1;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pow_2[i] = (pow_2[i-1]*2)%mod;
    }
    compress();

    ST[0].update(1 , 0 , n + 1 , 0 , {0, 1});
    ST[1].update(1 , 0 , n + 1 , n+1 , {0 , 1});

    for(int i = n; i > 1; i--)
    {
        pii tmp = ST[1].get(1 , 0 , n+1 , a[i] + 1 , n + 1);
        res_up[a[i]] = merging(res_up[a[i]] , {tmp.fi+1 , tmp.se});
        ST[1].update(1 , 0 , n+1 , a[i] , res_up[a[i]]);

        tmp = ST[0].get(1 , 0 , n+1 , 0 , a[i] - 1);
        res_do[a[i]] = merging(res_do[a[i]] , {tmp.fi+1 , tmp.se});
        ST[0].update(1 , 0 , n+1 , a[i] , res_do[a[i]]);
    }
    res_do[0] = {0 , 1};
    res_up[n+1] = {0 , 1};

    for(int i = n+1; i >= 1; i--)
    {
        suf[i] = merging(suf[i+1] , res_up[i]);
    }

    for(int i = 0; i <= n; i++)
    {
        int len = res_do[i].fi + suf[i+1].fi;
        int ways = (res_do[i].se * suf[i+1].se)%mod;
        (ways *= pow_2[n - 1 - len]) %= mod;
        //cout << len << ' ' << ways << '\n';
        ans = merging(ans , {len , ways});
    }

    int len = ST[0].get(1 , 0 , n+1 , 0 , a[1] - 1).fi + ST[1].get(1 , 0 , n+1 , a[1]+1 , n+1).fi + 1;
    int ways = (ST[0].get(1 , 0 , n+1 , 0 , a[1] - 1).se*ST[1].get(1 , 0 , n+1 , a[1]+1 , n+1).se)%mod;
    ways *= pow_2[n - len];

    ans = merging(ans , {len , ways});
    assert(ans.fi <= n);

    cout << ans.fi << ' ' << ans.se << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen("inp.txt", "r" , stdin);
    //freopen("out.txt", "w" , stdout);
    solve();
    return 0;
}

• Subtask 1: 91 / 140