Submission #1119636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119636		Thunnus	Zoltan (COCI16_zoltan)	C++17	42 / 140	253 ms	24256 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 Node{
    int len, cnt;
    Node(int l, int c) : len(l), cnt(c % MOD) {}
    Node() : Node(0, 0) {}
    inline Node combine(Node &other){
        if(len == other.len) return {len, (cnt + other.cnt) % MOD};
        else if(len > other.len) return {len, cnt};
        else return {other.len, other.cnt};
    }
};

struct SegTree{
    vector<Node> st;
    SegTree(int n) : st(4 * n) {}

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

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

    inline Node query(int ql, int qr, int v, int tl, int tr){
        if(ql > tr || tl > qr) return Node(LLONG_MIN, LLONG_MIN);
        if(tl >= ql && tr <= qr) return st[v];
        int mid = (tl + tr) / 2;
        Node left = query(ql, qr, 2 * v, tl, mid), right = query(ql, qr, 2 * v + 1, mid + 1, tr);
        return left.combine(right);
    }
};
 
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);
    vector<Node> suff_lis(n), pref_lds(n);
    for(int i = n - 1; i >= 0; i--){
        Node node = st.query(a[i] + 1, n + 1, 1, 1, n + 1);
        if(++node.len == 1) node.cnt = 1;
        suff_lis[i] = node;
        st.update(a[i], suff_lis[i], 1, 1, n + 1);
    }
    st.reset();
    for(int i = 0; i < n; i++){
        Node node = st.query(a[i] + 1, n + 1, 1, 1, n + 1);
        if(++node.len == 1) node.cnt = 1; 
        pref_lds[i] = node;
        st.update(a[i], pref_lds[i], 1, 1, n + 1);
    }

    Node mx;
    for(int i = 0; i < n; i++){
        Node temp(pref_lds[i].len + suff_lis[i].len - 1, (pref_lds[i].cnt * suff_lis[i].cnt) % MOD);
        mx = mx.combine(temp);
    }
    cout << mx.len << " " << (mx.cnt * binpow(2, n - mx.len)) % MOD << "\n";
    return 0;
}

• Subtask 1: 42 / 140