oj.uz

Submission #140608

# Submission time Handle Problem Language Result Execution time Memory
140608 2019-08-03T18:01:37 Z Minnakhmetov Zoltan (COCI16_zoltan) C++14
133 / 140
 348 ms 10040 KB 
#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 = que(0, vd.size() - 1), 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
133.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 6552 KB Output is correct
6 Incorrect 8 ms 6648 KB Output isn't 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 209 ms 9324 KB Output is correct
12 Correct 184 ms 8944 KB Output is correct
13 Correct 164 ms 8756 KB Output is correct
14 Correct 221 ms 8948 KB Output is correct
15 Correct 300 ms 9412 KB Output is correct
16 Correct 348 ms 10040 KB Output is correct
17 Correct 275 ms 10024 KB Output is correct
18 Correct 273 ms 9840 KB Output is correct
19 Correct 274 ms 9844 KB Output is correct
20 Correct 275 ms 9840 KB Output is correct