Submission #1119620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119620		Thunnus	Zoltan (COCI16_zoltan)	C++17	21 / 140	1073 ms	14704 KiB

zoltan

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int MOD = 1e9 + 7;

inline int binpow(int a, int b){
    int ret = 1;
    while(b){
        if(b & 1){
            ret = (ret * a) % MOD;
        }
        a = (a * a) % MOD;
        b >>= 1;
    }
    return ret;
}

struct SegTree{
    vi st;
    SegTree(int n) : st(4 * n) {}

    inline void reset(){
        fill(st.begin(), st.end(), 0);
        return;
    }

    inline void update(int pos, int val, int v, int tl, int tr){
        if(tl == tr){
            st[v] += val;
            return;
        }
        int mid = (tl + tr) / 2;
        if(pos <= mid){
            update(pos, val, 2 * v, tl, mid);
        }
        else{
            update(pos, val, 2 * v + 1, mid + 1, tr);
        }
        st[v] = max(st[2 * v], st[2 * v + 1]);
        return;
    }

    inline int query(int ql, int qr, int v, int tl, int tr){
        if(ql > tr || tl > qr) return LLONG_MIN;
        if(tl >= ql && tr <= qr) return st[v];
        int mid = (tl + tr) / 2;
        return max(query(ql, qr, 2 * v, tl, mid), query(ql, qr, 2 * v + 1, mid + 1, tr));
    }
};
 
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
    vi a(n), c;
    for(int &i : a){
        cin >> i;
        c.emplace_back(i);
    }
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());

    auto compress = [&](int val) -> int {
        return lower_bound(c.begin(), c.end(), val) - c.begin();
    };

    for(int i = 0; i < n; i++){
        a[i] = compress(a[i]) + 1;
    }

    SegTree st(n + 1);
    vi suff_lis(n), pref_lds(n);
    for(int i = n - 1; i >= 0; i--){
        suff_lis[i] = 1 + st.query(a[i] + 1, n + 1, 1, 1, n + 1);
        st.update(a[i], suff_lis[i], 1, 1, n + 1);
    }
    st.reset();
    for(int i = 0; i < n; i++){
        pref_lds[i] = 1 + st.query(a[i] + 1, n + 1, 1, 1, n + 1);
        st.update(a[i], pref_lds[i], 1, 1, n + 1);
    }

    pii mx = {0, 0};
    for(int i = 0; i < n; i++){
        if(pref_lds[i] + suff_lis[i] - 1 > mx.fi){
            mx.fi = pref_lds[i] + suff_lis[i] - 1;
            mx.se = 1;
        }
        else if(pref_lds[i] + suff_lis[i] - 1 == mx.fi){
            mx.se++;
        }
    }
    cout << mx.fi << " " << (mx.se * binpow(2, n - mx.fi)) % MOD << "\n";
    return 0;
}

• Subtask 1: 21 / 140