Submission #253963

#	Time	Username	Problem	Language	Result	Execution time	Memory
253963		NONAME	Zoltan (COCI16_zoltan)	C++14	133 / 140	127 ms	9960 KiB

zoltan

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