oj.uz

답안 #130469

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130469 2019-07-15T09:21:29 Z forestryks Zoltan (COCI16_zoltan) C++14
140 / 140
 543 ms 19232 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define left left123
#define right right123

const int MAXN = 2e5 + 5;
const int mod = 1e9 + 7;

int n;
int a[MAXN];
pll t[MAXN * 4];
pll dpup[MAXN];
pll dpdown[MAXN];
ll pw[MAXN];

pll merge(const pll &a, const pll &b) {
    if (a.f == b.f) return {a.f, (a.s + b.s) % mod};
    return max(a, b);
}

void build(int v, int tl, int tr) {
    t[v] = {0, 0};
    if (tr - tl == 1) return;
    int tm = tl + (tr - tl) / 2;
    build(v * 2 + 1, tl, tm);
    build(v * 2 + 2, tm, tr);
    // for (int i = tl; i < tr; ++i) {
    //     t[i] = {0, 0};
    // }
}

void upd(int v, int tl, int tr, int p, pll x) {
    if (tr - tl == 1) {
        t[v] = merge(t[v], x);
        return;
    }

    int tm = tl + (tr - tl) / 2;
    if (p < tm) {
        upd(v * 2 + 1, tl, tm, p, x);
    } else {
        upd(v * 2 + 2, tm, tr, p, x);
    }
    t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
    // t[p] = merge(t[p], x);
}

pll get(int v, int tl, int tr, int l, int r) {
    if (r <= tl || tr <= l) return {0, 0};
    if (l <= tl && tr <= r) return t[v];

    int tm = tl + (tr - tl) / 2;
    return merge(get(v * 2 + 1, tl, tm, l, r), get(v * 2 + 2, tm, tr, l, r));
    // pll best = {0, 0};
    // for (int i = l; i < r; ++i) {
    //     best = merge(best, t[i]);
    // }
    // return best;
}

void compress() {
    vector<int> x;
    rep(i, n) {
        x.push_back(a[i]);
    }
    sort(all(x));
    x.resize(unique(all(x)) - x.begin());
    rep(i, n) {
        a[i] = lower_bound(all(x), a[i]) - x.begin();
    }
}

int main() {
    pw[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        pw[i] = (pw[i - 1] * 2) % mod;
    }

    FAST_IO;
    cin >> n;
    rep(i, n) {
        cin >> a[i];
    }

    compress();

    for (int i = n - 1; i >= 0; --i) {
        dpup[i] = max(make_pair(0LL, 1LL), get(0, 0, n, a[i] + 1, n));
        dpup[i].f++;
        upd(0, 0, n, a[i], dpup[i]);
    }

    build(0, 0, n);
    for (int i = n - 1; i >= 0; --i) {
        // cout << i << " : " << get(0, 0, n, 0, a[i]).f << endl;
        dpdown[i] = max(make_pair(0LL, 1LL), get(0, 0, n, 0, a[i]));
        dpdown[i].f++;
        upd(0, 0, n, a[i], dpdown[i]);
    }

    // rep(i, n) {
    //     cout << "(" << dpup[i].f << ' ' << dpup[i].s << ") ";
    // }
    // cout << endl;
    // rep(i, n) {
    //     cout << "(" << dpdown[i].f << ' ' << dpdown[i].s << ") ";
    // }
    // cout << endl;
    pll ans = {0, 1};
    rep(i, n) {
        pll nw = {dpup[i].f, (dpup[i].s * pw[n - dpup[i].f - (i != 0)]) % mod};
        ans = merge(ans, nw);

        if (i == 0) continue;
        nw = {dpdown[i].f, (dpdown[i].s * pw[n - dpdown[i].f - (i != 0)]) % mod};
        ans = merge(ans, nw);
    }

    // if (ans.f == 1) {
    //     ans = {1, n};
    // }i 

    build(0, 0, n + 1);
    for (int i = 1; i < n; ++i) {
        upd(0, 0, n + 1, a[i], dpdown[i]);
    }

    rep(i, n) {
        pll nw = get(0, 0, n + 1, 0, a[i]);
        nw.f += dpup[i].f;
        nw.s *= dpup[i].s;
        nw.s %= mod;

        if (i == 0) {
            nw.s *= pw[n - nw.f];
        } else {
            nw.s *= pw[n - 1 - nw.f];
        }
        nw.s %= mod;
        ans = merge(ans, nw);
    }

    // for (int i = n - 1; i >= 0; --i) {
    //     // if (dpup[i].f == 1) continue;
    //     for (int j = 1; j < n; ++j) {
    //         if (i == j) continue;
    //         if (a[j] >= a[i]) continue;

    //         pll nw = {dpup[i].f + dpdown[j].f, (dpup[i].s * dpdown[j].s) % mod};
    //         // cout << nw.f << ' ' << nw.s << endl;
    //         if (i == 0) {
    //             nw.s *= pw[n - nw.f];
    //         } else {
    //             nw.s *= pw[n - 1 - nw.f];
    //         }
    //         nw.s %= mod;
    //         ans = merge(ans, nw);
    //     }
    // }

    if (ans.f == 1) {
        ans = {1, pw[n - 1] * n};
        ans.s %= mod;
    }

    cout << ans.f << ' ' << ans.s << endl;
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1912 KB Output is correct
2 Correct 4 ms 1912 KB Output is correct
3 Correct 4 ms 1912 KB Output is correct
4 Correct 4 ms 1912 KB Output is correct
5 Correct 4 ms 1888 KB Output is correct
6 Correct 4 ms 1912 KB Output is correct
7 Correct 5 ms 2040 KB Output is correct
8 Correct 5 ms 2040 KB Output is correct
9 Correct 6 ms 2040 KB Output is correct
10 Correct 6 ms 2040 KB Output is correct
11 Correct 324 ms 17080 KB Output is correct
12 Correct 291 ms 16264 KB Output is correct
13 Correct 251 ms 11724 KB Output is correct
14 Correct 345 ms 16472 KB Output is correct
15 Correct 478 ms 18204 KB Output is correct
16 Correct 543 ms 19232 KB Output is correct
17 Correct 422 ms 18500 KB Output is correct
18 Correct 437 ms 18640 KB Output is correct
19 Correct 418 ms 18692 KB Output is correct
20 Correct 432 ms 18640 KB Output is correct