Submission #140604

#	Time	Username	Problem	Language	Result	Execution time	Memory
140604		Minnakhmetov	Zoltan (COCI16_zoltan)	C++14	21 / 140	349 ms	11756 KiB

zoltan

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

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int MOD = 1e9 + 7;

struct Node {
    int val, w;
};

Node operator + (Node a, Node b) {
    if (a.val == b.val) {
        Node c = { a.val, a.w + b.w };
        if (c.w >= MOD)
            c.w -= MOD;
        return c;
    }
    if (a.val > b.val)
        return a;
    return b;
}

const int N = 2e5 + 5;
Node t[N * 4], mxr[N], mxl[N];
vector<int> vd;
int a[N];

void upd(int x, Node y, int v = 1, int L = 0, int R = vd.size() - 1) {
    if (L == R) {
        t[v] = y;
    }
    else {
        int m = (L + R) >> 1;
        if (x <= m)
            upd(x, y, v * 2, L, m);
        else
            upd(x, y, v * 2 + 1, m + 1, R);
        t[v] = t[v * 2] + t[v * 2 + 1];
    }
}

Node que(int l, int r, int v = 1, int L = 0, int R = vd.size() - 1) {
    if (l > r)
        return { 0, 1 };
    if (l == L && r == R) {
        return t[v];
    }
    int m = (L + R) >> 1;
    return que(l, min(m, r), v * 2, L, m) + 
        que(max(m + 1, l), r, v * 2 + 1, m + 1, R);
}

signed main() { 
#ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        vd.push_back(a[i]);
    }

    sort(all(vd));
    vd.erase(unique(all(vd)), vd.end());

    for (int i = 0; i < n; i++)  {
        a[i] = lower_bound(all(vd), a[i]) - vd.begin();
    }

    fill(t, t + N * 4, (Node){ 0, 1 });

    for (int i = n - 1; i >= 0; i--) {
        Node res = que(a[i] + 1, vd.size() - 1);
        res.val++;
        upd(a[i], res);
        mxr[i] = res;
    }

    fill(t, t + N * 4, (Node){ 0, 1 });

    for (int i = n - 1; i > 0; i--) {
        Node res = que(0, a[i] - 1);
        res.val++;
        upd(a[i], res);
    }

    Node mx_subseq = { 0, 0 }, mx_subseq_with_first = { 0, 0 }; 

    for (int i = 0; i < n; i++) {
        Node cur = que(0, a[i] - 1);

        cur.val += mxr[i].val;
        cur.w = cur.w * (ll)mxr[i].w % MOD;

        if (i == 0)
            mx_subseq_with_first = mx_subseq_with_first + cur;
        else
            mx_subseq = mx_subseq + cur;
    }

    

    for (int i = 0; i < n - 1 - (mx_subseq.val > 1 ? mx_subseq.val : 0); i++) {
        mx_subseq.w = mx_subseq.w * 2 % MOD;
    }

    for (int i = 0; i < n - mx_subseq_with_first.val; i++) {
        mx_subseq_with_first.w = mx_subseq_with_first.w * 2 % MOD;
    }

    Node ans = mx_subseq + mx_subseq_with_first;

    cout << ans.val << " " << ans.w;


    return 0;
}

• Subtask 1: 21 / 140