Submission #877201

#	Time	Username	Problem	Language	Result	Execution time	Memory
877201		noiaint	Zoltan (COCI16_zoltan)	C++17	140 / 140	94 ms	10892 KiB

zoltan

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 2e5 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n;
int a[N];
pair<int, int> f[N], g[N];
pair<int, int> bit[N][2];
int pw2[N];

void unite(pair<int, int> &x, pair<int, int> y) {
    if (x.fi < y.fi) x = y;
    else if (x.fi == y.fi) x.se = (x.se + y.se) % mod;
}

void update(bool op, int u, pair<int, int> c) {
    if (op) {
        for (; u > 0; u -= u & (-u)) unite(bit[u][op], c);
    } else {
        for (; u <= n; u += u & (-u)) unite(bit[u][op], c);
    }
}
pair<int, int> get(bool op, int u) {
    pair<int, int> res = mp(0, 1);
    if (op) {
        for (; u <= n; u += u & (-u)) unite(res, bit[u][op]);
    } else {
        for (; u > 0; u -= u & (-u)) unite(res, bit[u][op]);
    }
    return res;
}

void process() {
    cin >> n;
    pw2[0] = 1;
    for (int i = 1; i <= n; ++i) pw2[i] = 1LL * pw2[i - 1] * 2 % mod;
    vector<int> values;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        values.push_back(a[i]);
    }
    sort(all(values));
    values.erase(unique(all(values)), values.end());
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(all(values), a[i]) - values.begin() + 1;

    pair<int, int> ans = mp(0, 0);
    for (int i = n; i >= 1; --i) {
        f[i] = get(0, a[i] - 1);
        g[i] = get(1, a[i] + 1);

        f[i].fi += 1;
        g[i].fi += 1;

        update(0, a[i], f[i]);
        update(1, a[i], g[i]);

        pair<int, int> cur;
        cur.fi = f[i].fi + g[i].fi - 1;
        cur.se = 1LL * pw2[n - (f[i].fi + g[i].fi - 1)] * f[i].se % mod * g[i].se % mod;
        unite(ans, cur);
    }

    cout << ans.fi << ' ' << ans.se;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    int tc = 1;
    // cin >> tc;
    
    while (tc--) {
        process();
    }

    return 0;
}

/*

*/

• Subtask 1: 140 / 140