oj.uz

Submission #1037148

# Submission time Handle Problem Language Result Execution time Memory
1037148 2024-07-28T09:01:22 Z BF001 Zoltan (COCI16_zoltan) C++17
140 / 140
 146 ms 22116 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define N 200005
#define fi first
#define se second

typedef pair<int, int> ii;

int md = 1e9 + 7;
 
struct fw{
    int n;
    vector<ii> bit;

    fw(int siz){
        n = siz;
        bit.resize(n + 1, {0, 0});
    }

    void add(ii& a, ii b){
        if (a.fi == b.fi){
            a.se = (a.se + b.se) % md;
        }
        else if (a.fi < b.fi) a.se = b.se;
        a.fi = max(a.fi, b.fi);
    }

    void ud1(int pos, ii val){
        while (pos <= n){
            add(bit[pos], val);
            pos += (pos & (-pos));
        }
    }

    ii get1(int pos){
        ii rt = {0, 1};
        while (pos >= 1){
            add(rt, bit[pos]);
            pos -= (pos & (-pos));
        }
        return rt;
    }

    void ud2(int pos, ii val){
        while (pos >= 1){
            add(bit[pos], val);
            pos -= (pos & (-pos));
        }
    }

    ii get2(int pos){
        ii rt = {0, 1};
        while (pos <= n){
            add(rt, bit[pos]);
            pos += (pos & (-pos));
        }
        return rt;
    }

};

void add(ii& a, ii b){
    if (a.fi == b.fi){
        a.se = (a.se + b.se) % md;
    }
    else if (a.fi < b.fi) a.se = b.se;
    a.fi = max(a.fi, b.fi);
}

int pw(int a, int n){
    int rt = 1;
    while (n){
        if (n & 1) rt = rt * a % md;
        a = a * a % md;
        n >>= 1;
    }
    return rt;
}

int n, a[N];
vector<int> cy;
map<int, int> dd;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        cy.push_back(a[i]);
    }

    sort(cy.begin(), cy.end());
    cy.resize(unique(cy.begin(), cy.end()) - cy.begin());

    int pos = 0;
    for (auto x : cy) dd[x] = ++pos;
    for (int i = 1; i <= n; i++){
        a[i] = dd[a[i]];
    }
    
    fw s1(pos), s2(pos);
    ii res = {0, 0};

    for (int i = n; i >= 1; i--){
        ii dp1 = s1.get1(a[i] - 1);
        ii dp2 = s2.get2(a[i] + 1);
        add(res, {dp1.fi + dp2.fi + 1, dp1.se * dp2.se % md});
        s1.ud1(a[i], {dp1.fi + 1, dp1.se});
        s2.ud2(a[i], {dp2.fi + 1, dp2.se});
    }

    cout << res.fi << " " << (res.se * pw(2, n - res.fi)) % md;

    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 82 ms 17604 KB Output is correct
12 Correct 71 ms 15300 KB Output is correct
13 Correct 66 ms 14544 KB Output is correct
14 Correct 95 ms 15348 KB Output is correct
15 Correct 130 ms 18988 KB Output is correct
16 Correct 146 ms 22116 KB Output is correct
17 Correct 99 ms 19180 KB Output is correct
18 Correct 99 ms 19144 KB Output is correct
19 Correct 95 ms 19144 KB Output is correct
20 Correct 101 ms 19140 KB Output is correct