Submission #140607

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
140607	2019-08-03T17:04:47 Z	Minnakhmetov	Zoltan (COCI16_zoltan)	C++14	140 / 140	354 ms	9944 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);
}

void brute() {
    Node ans = { 0, 1 };
    deque<int> q;
    for (int i = 0; i < (1 << (n - 1)); i++) {
        q = { a[0] };
        for (int j = 1; j < n; j++) {
            if ((i >> (j - 1)) & 1)
                q.push_back(a[j]);
            else
                q.push_front(a[j]);
        }

        fill(t, t + vd.size() * 4, (Node){ 0, 1 });

        Node cur = { 0, 1 };

        for (int j = 0; j < n; j++) {
            Node res = que(0, q[j] - 1);
            res.val++;
            upd(q[j], res);
            ans = ans + res;

            cur = cur + res;
        }
    }

    cout << ans.val << " " << ans.w << "\n";
}

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));

    // cout << n << "\n";
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        // a[i] = rnd() % 10 + 1;
        // cout << a[i] << " ";
        vd.push_back(a[i]);
    }
    // cout << "\n";

    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();
    }

    // brute();

    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;

        // cout << "! " << cur.val << " " << cur.w << "\n";
        // cout << "! " << mxr[i].val << " " << mxr[i].w << "\n";

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

    // cout << "!" << mx_subseq.val << " " << mx_subseq.w << "\n";
    // cout << mx_subseq_with_first.val << " " << mx_subseq_with_first.w << "\n";

    // for (int i = 0; i < n; i++) {
    //     cout << mxr[i].val << " " << mxr[i].w << "\n";
    // }
    // cout << "\n";

    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	6620 KB	Output is correct
9	Correct	9 ms	6648 KB	Output is correct
10	Correct	9 ms	6648 KB	Output is correct
11	Correct	208 ms	9304 KB	Output is correct
12	Correct	176 ms	8940 KB	Output is correct
13	Correct	167 ms	8820 KB	Output is correct
14	Correct	226 ms	9044 KB	Output is correct
15	Correct	294 ms	9452 KB	Output is correct
16	Correct	354 ms	9944 KB	Output is correct
17	Correct	274 ms	9908 KB	Output is correct
18	Correct	283 ms	9840 KB	Output is correct
19	Correct	270 ms	9836 KB	Output is correct
20	Correct	283 ms	9908 KB	Output is correct