Submission #130469

#	Time	Username	Problem	Language	Result	Execution time	Memory
130469		forestryks	Zoltan (COCI16_zoltan)	C++14	140 / 140	543 ms	19232 KiB

zoltan

#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 / 140