oj.uz

답안 #140610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140610 2019-08-03T18:18:33 Z Minnakhmetov Zoltan (COCI16_zoltan) C++14
140 / 140
 343 ms 9968 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);
}

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

# 결과 실행 시간 메모리 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