oj.uz

답안 #140604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140604 2019-08-03T16:40:57 Z Minnakhmetov Zoltan (COCI16_zoltan) C++14
21 / 140
 349 ms 11756 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], mxl[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] = 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 = 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
21.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 6648 KB Output isn't correct
2 Incorrect 9 ms 6656 KB Output isn't correct
3 Incorrect 8 ms 6648 KB Output isn't correct
4 Correct 8 ms 6648 KB Output is correct
5 Correct 9 ms 6564 KB Output is correct
6 Correct 8 ms 6648 KB Output is correct
7 Incorrect 9 ms 6648 KB Output isn't correct
8 Incorrect 9 ms 6648 KB Output isn't correct
9 Incorrect 11 ms 6648 KB Output isn't correct
10 Incorrect 9 ms 6648 KB Output isn't correct
11 Incorrect 204 ms 10480 KB Output isn't correct
12 Incorrect 184 ms 10116 KB Output isn't correct
13 Incorrect 163 ms 9716 KB Output isn't correct
14 Incorrect 235 ms 10220 KB Output isn't correct
15 Incorrect 299 ms 11128 KB Output isn't correct
16 Incorrect 349 ms 11756 KB Output isn't correct
17 Incorrect 278 ms 11116 KB Output isn't correct
18 Incorrect 274 ms 11184 KB Output isn't correct
19 Incorrect 269 ms 11116 KB Output isn't correct
20 Incorrect 271 ms 11116 KB Output isn't correct