oj.uz

Submission #1108886

# Submission time Handle Problem Language Result Execution time Memory
1108886 2024-11-05T15:17:18 Z vjudge1 Zoltan (COCI16_zoltan) C++17
140 / 140
 386 ms 30148 KB 
#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];
long long 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
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 1 ms 6480 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 2 ms 6480 KB Output is correct
6 Correct 1 ms 6480 KB Output is correct
7 Correct 3 ms 6480 KB Output is correct
8 Correct 3 ms 6648 KB Output is correct
9 Correct 2 ms 6480 KB Output is correct
10 Correct 2 ms 6480 KB Output is correct
11 Correct 241 ms 26820 KB Output is correct
12 Correct 199 ms 25840 KB Output is correct
13 Correct 183 ms 20384 KB Output is correct
14 Correct 254 ms 25796 KB Output is correct
15 Correct 357 ms 27952 KB Output is correct
16 Correct 386 ms 30148 KB Output is correct
17 Correct 285 ms 28612 KB Output is correct
18 Correct 270 ms 28820 KB Output is correct
19 Correct 289 ms 28768 KB Output is correct
20 Correct 300 ms 28824 KB Output is correct