oj.uz

Submission #253966

# Submission time Handle Problem Language Result Execution time Memory
253966 2020-07-29T07:39:38 Z NONAME Zoltan (COCI16_zoltan) C++14
140 / 140
 128 ms 8172 KB 
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;

const int N = int(2e5) + 500;
const int base = int(1e9) + 7;

int n, m, ans;
int a[N];
pair <int, int> fen[N];
vector <pair <int, int> > lft, rgt;

int mul(int x, int y) { return (x * 1ll * y) % ll(base); }

int sum(int x, int y) { return (x + y) % base; }

int bin_pow(int x, int st) {
    int res = 1;
    while (st) {
        if (st & 1)
            res = mul(res, x);
        x = mul(x, x);
        st >>= 1;
    }
    return res;
}

void upd(pair <int, int> &x, pair <int, int> &y) {
    if (y.first >= x.first) {
        if (x.first == y.first) x.second = sum(x.second, y.second);
            else x = y;
    }
}

void fen_upd(int _x, pair <int, int> vl) {
    while (_x < n) {
        upd(fen[_x], vl);
        _x = (_x | (_x + 1));
    }
}

pair <int, int> fen_get(int _x) {
    pair <int, int> res = make_pair(0, 0);
    while (_x >= 0) {
        upd(res, fen[_x]);
        _x = (_x & (_x + 1)) - 1;
    }
    return res;
}

void calc(vector <pair <int, int> > &cur) {
    for (int i = 0; i < n; ++i)
        fen[i] = make_pair(0, 0);

    for (int i = 0; i < n; ++i) {
        cur.push_back(make_pair(0, 1));
        pair <int, int> val = fen_get(a[i] - 1);
        upd(cur.back(), val);
        ++(cur.back()).first;
        fen_upd(a[i], cur.back());
    }
}

int main() {
    fast_io;

    cin >> n;
    vector <int> b;
    for (int i = 0; i < n; ++i)
        cin >> a[n - 1 - i], b.push_back(a[n - 1 - i]);

    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());

    for (int i = 0; i < n; ++i)
        a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();

    //for (int i = 0; i < n; ++i)
        //cerr << a[i] << " ";
    //cerr << "\n\n";
    calc(lft);
    //for (int i = 0; i < n; ++i)
        //cerr << lft[i].first << " " << lft[i].second << "\n";
    //cerr << "\n";
    for (int i = 0; i < n; ++i)
        a[i] = int(b.size()) - 1 - a[i];
    calc(rgt);

    for (int i = 0; i < n; ++i)
        m = max(m, lft[i].first + rgt[i].first - 1);

    for (int i = 0; i < n; ++i) {
        if (lft[i].first + rgt[i].first - 1 < m)
            continue;

        ans = sum(ans, mul(lft[i].second, rgt[i].second));
    }

    ans = mul(ans, bin_pow(2, n - m));

    cout << m << " " << ans << "\n";
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 77 ms 7148 KB Output is correct
12 Correct 65 ms 6636 KB Output is correct
13 Correct 59 ms 4976 KB Output is correct
14 Correct 90 ms 6788 KB Output is correct
15 Correct 108 ms 7400 KB Output is correct
16 Correct 128 ms 8156 KB Output is correct
17 Correct 90 ms 8168 KB Output is correct
18 Correct 94 ms 8172 KB Output is correct
19 Correct 88 ms 8172 KB Output is correct
20 Correct 88 ms 8172 KB Output is correct