oj.uz

Submission #140606

# Submission time Handle Problem Language Result Execution time Memory
140606 2019-08-03T16:49:35 Z Minnakhmetov Zoltan (COCI16_zoltan) C++14
21 / 140
 351 ms 10888 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) {
        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];

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

    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 = 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
21.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6648 KB Output isn't correct
2 Incorrect 8 ms 6648 KB Output isn't correct
3 Incorrect 8 ms 6648 KB Output isn't correct
4 Correct 10 ms 6620 KB Output is correct
5 Correct 8 ms 6648 KB Output is correct
6 Correct 8 ms 6648 KB Output is correct
7 Incorrect 11 ms 6648 KB Output isn't correct
8 Incorrect 9 ms 6648 KB Output isn't correct
9 Incorrect 10 ms 6648 KB Output isn't correct
10 Incorrect 9 ms 6652 KB Output isn't correct
11 Incorrect 225 ms 10248 KB Output isn't correct
12 Incorrect 179 ms 9964 KB Output isn't correct
13 Incorrect 166 ms 9844 KB Output isn't correct
14 Incorrect 229 ms 10068 KB Output isn't correct
15 Incorrect 295 ms 10516 KB Output isn't correct
16 Incorrect 351 ms 10888 KB Output isn't correct
17 Incorrect 275 ms 10864 KB Output isn't correct
18 Incorrect 274 ms 10876 KB Output isn't correct
19 Incorrect 273 ms 10860 KB Output isn't correct
20 Incorrect 289 ms 10860 KB Output isn't correct