oj.uz

답안 #140607

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140607 2019-08-03T17:04:47 Z Minnakhmetov Zoltan (COCI16_zoltan) C++14
140 / 140
 354 ms 9944 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 = { 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

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