oj.uz

Submission #253963

# Submission time Handle Problem Language Result Execution time Memory
253963 2020-07-29T07:36:41 Z NONAME Zoltan (COCI16_zoltan) C++14
133 / 140
 127 ms 9960 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
133.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 0 ms 384 KB Output isn't correct
6 Correct 1 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 2 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 77 ms 8300 KB Output is correct
12 Correct 72 ms 7644 KB Output is correct
13 Correct 61 ms 5872 KB Output is correct
14 Correct 88 ms 8040 KB Output is correct
15 Correct 109 ms 9068 KB Output is correct
16 Correct 127 ms 9960 KB Output is correct
17 Correct 92 ms 9448 KB Output is correct
18 Correct 107 ms 9440 KB Output is correct
19 Correct 92 ms 9324 KB Output is correct
20 Correct 97 ms 9400 KB Output is correct