Submission #140610

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
140610	2019-08-03T18:18:33 Z	Minnakhmetov	Zoltan (COCI16_zoltan)	C++14	140 / 140	343 ms	9968 KB

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) {
        if (a.val == 0)
            return { 0, 1 };
        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];
vector<int> vd;
int a[N];
int n;

void upd(int x, Node y, int v = 1, int L = 0, int R = vd.size() - 1) {
    if (L == R) {
        t[v] = 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);

    cin >> n;

    mt19937 rnd(time(0));

    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 = que(0, vd.size() - 1), mx_subseq_with_first = { 0, 0 }; 

    if (mx_subseq.val == 1)
        mx_subseq = { 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 = 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

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	6648 KB	Output is correct
2	Correct	8 ms	6648 KB	Output is correct
3	Correct	8 ms	6648 KB	Output is correct
4	Correct	8 ms	6648 KB	Output is correct
5	Correct	8 ms	6652 KB	Output is correct
6	Correct	8 ms	6648 KB	Output is correct
7	Correct	9 ms	6648 KB	Output is correct
8	Correct	9 ms	6652 KB	Output is correct
9	Correct	9 ms	6648 KB	Output is correct
10	Correct	9 ms	6648 KB	Output is correct
11	Correct	204 ms	9212 KB	Output is correct
12	Correct	176 ms	8944 KB	Output is correct
13	Correct	162 ms	8692 KB	Output is correct
14	Correct	218 ms	8900 KB	Output is correct
15	Correct	280 ms	9456 KB	Output is correct
16	Correct	343 ms	9940 KB	Output is correct
17	Correct	340 ms	9840 KB	Output is correct
18	Correct	280 ms	9968 KB	Output is correct
19	Correct	268 ms	9836 KB	Output is correct
20	Correct	270 ms	9836 KB	Output is correct