Submission #1037141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037141		BF001	Zoltan (COCI16_zoltan)	C++17	49 / 140	153 ms	24004 KiB

zoltan

#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, dp2.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: 49 / 140