Submission #98540

#	Time	Username	Problem	Language	Result	Execution time	Memory
98540		dalgerok	Zoltan (COCI16_zoltan)	C++17	140 / 140	311 ms	9452 KiB

zoltan

#include<bits/stdc++.h>
using namespace std;



const int N = 2e5 + 5, MOD = 1e9 + 7;




int n, m, a[N];
pair < int, int > b[N], c[N], t[4 * N];



vector < int > e;
inline int Find(int x){
    return lower_bound(e.begin(), e.end(), x) - e.begin() + 1;
}


void build(int v, int l, int r){
    t[v] = make_pair(-1, -1);
    if(l == r){
        return;
    }
    int mid = (r + l) >> 1;
    build(v + v, l, mid);
    build(v + v + 1, mid + 1, r);
}

inline pair < int, int > comb(pair < int, int > a, pair < int, int > b){
    if(a.first == -1){
        return b;
    }
    if(b.first == -1){
        return a;
    }
    int mx = max(a.first, b.first);
    int cur = 0;
    if(mx == a.first){
        cur += a.second;
        if(cur >= MOD){
            cur -= MOD;
        }
    }
    if(mx == b.first){
        cur += b.second;
        if(cur >= MOD){
            cur -= MOD;
        }
    }
    return make_pair(mx, cur);
}

pair < int, int > get(int v, int l, int r, int tl, int tr){
    if(l > r || l > tr || tl > r || tl > tr){
        return make_pair(-1, -1);
    }
    if(tl <= l && r <= tr){
        return t[v];
    }
    int mid = (r + l) >> 1;
    return comb(get(v + v, l, mid, tl, tr), get(v + v + 1, mid + 1, r, tl, tr));
}

void update(int v, int l, int r, int pos, pair < int, int > val){
    if(l == r){
        t[v] = comb(t[v], val);
        return;
    }
    int mid = (r + l) >> 1;
    if(pos <= mid){
        update(v + v, l, mid, pos, val);
    }
    else{
        update(v + v + 1, mid + 1, r, pos, val);
    }
    t[v] = comb(t[v + v], t[v + v + 1]);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        e.push_back(a[i]);
    }
    sort(e.begin(), e.end());
    e.resize(unique(e.begin(), e.end()) - e.begin());
    m = (int)e.size();
    for(int i = 1; i <= n; i++){
        a[i] = Find(a[i]);
    }
    build(1, 1, n);
    for(int i = n; i >= 1; i--){
        auto it = get(1, 1, m, 1, a[i] - 1);
        if(it.first == -1){
            it.first = 0;
            it.second = 1;
        }
        it.first += 1;
        b[i] = it;
        update(1, 1, m, a[i], it);
    }
    build(1, 1, n);
    for(int i = n; i >= 1; i--){
        auto it = get(1, 1, m, a[i] + 1, m);
        if(it.first == -1){
            it.first = 0;
            it.second = 1;
        }
        it.first += 1;
        c[i] = it;
        update(1, 1, m, a[i], it);
    }
    pair < int, int > kek = make_pair(-1, -1);
    for(int i = 1; i <= n; i++){
        kek = comb(kek, make_pair(b[i].first - 1 + c[i].first, 1LL * b[i].second * c[i].second % MOD));
    }
    for(int i = 1; i <= n - kek.first; i++){
        kek.second = 2LL * kek.second % MOD;
    }
    cout << kek.first << " " << kek.second;
}

• Subtask 1: 140 / 140