oj.uz

Submission #1108885

# Submission time Handle Problem Language Result Execution time Memory
1108885 2024-11-05T15:16:01 Z vjudge1 Zoltan (COCI16_zoltan) C++17
42 / 140
 397 ms 29636 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], 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
42.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 2 ms 6480 KB Output is correct
4 Correct 2 ms 6480 KB Output is correct
5 Correct 2 ms 6480 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Incorrect 3 ms 6480 KB Output isn't correct
8 Incorrect 3 ms 6480 KB Output isn't correct
9 Incorrect 2 ms 6480 KB Output isn't correct
10 Incorrect 2 ms 6480 KB Output isn't correct
11 Incorrect 239 ms 26540 KB Output isn't correct
12 Incorrect 214 ms 25284 KB Output isn't correct
13 Incorrect 176 ms 20500 KB Output isn't correct
14 Incorrect 250 ms 25428 KB Output isn't correct
15 Incorrect 340 ms 27588 KB Output isn't correct
16 Incorrect 397 ms 29636 KB Output isn't correct
17 Incorrect 306 ms 27676 KB Output isn't correct
18 Incorrect 293 ms 27588 KB Output isn't correct
19 Incorrect 298 ms 27652 KB Output isn't correct
20 Incorrect 317 ms 27400 KB Output isn't correct