Submission #625218

#	Time	Username	Problem	Language	Result	Execution time	Memory
625218		minhi1	Zoltan (COCI16_zoltan)	C++14	14 / 140	75 ms	30940 KiB

zoltan

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define forn(i, a, b) for (int i = (a); i <= (b); ++i)
#define forb(i, b, a) for (int i = (b); i >= (a); --i)
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
template<class X, class Y> bool ckmax(X &x, Y y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template<class X, class Y> bool ckmin(X &x, Y y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
const int inf = (int)1e9 + 25;
const ll linf = 1e18;
const int N = 2e5 + 25;
/////////////////////////////////////////////////////
const int MOD = (int)1e9 + 7;
pair<int, int> comb(const pair<int, int> &x, const pair<int, int> &y) {
    if (x.first == y.first) return {x.first, (x.second + y.second) % MOD};
    return max(x, y);
}
void combed(pair<int, int> &x, pair<int, int> &y) {
    if (x.first == y.first) (x.second += y.second) %= MOD;
    else if (x.first < y.first) x = y;
}
struct segmentTree {
    int n;
    vector<pair<int, int>> mx;
    segmentTree(int _n = 0) {
        n = _n;
        mx.assign(4 * n + 6, {-1, 0});
    }
    void upd(int i, int l, int r, int p, pair<int, int> v) {
        if (l > r) return;
        if (l == r) {
            combed(mx[i], v);
            return;
        }
        int mid = (l + r) >> 1;
        if (p > mid) upd(i << 1 | 1, mid + 1, r, p, v);
        else upd(i << 1, l, mid, p, v);
        mx[i] = comb(mx[i << 1], mx[i << 1 | 1]);
    }
    void upd(int p, pair<int, int> v) {
        upd(1, 1, n, p, v);
    }
    pair<int, int> get(int i, int l, int r, int u, int v) {
        if (l > r || u > v || l > v || r < u) return {0, 0};
        if (l >= u && r <= v) return mx[i];
        int mid = (l + r) >> 1;
        pair<int, int> L = get(i << 1, 1, mid, u, v), R = get(i << 1 | 1, mid + 1, r, u, v);
        return comb(L, R);
    }
    pair<int, int> get(int u, int v) {
        return comb(get(1, 1, n, u, v), {0, 1});
    }
};
int n, a[N];
vector<int> values;
void compress() {
    sort(values.begin(), values.end());
    values.resize(unique(values.begin(), values.end()) - values.begin());
    forn(i, 1, n) a[i] = lower_bound(values.begin(), values.end(), a[i]) - values.begin() + 1;
}
void sol() {
    cin >> n;
    forn(i, 1, n) cin >> a[i], values.pb(a[i]);
    compress();
    int m = values.size();
    int res = 0;
    ll tot = 0;
    segmentTree inc(m), dec(m);
    forb(i, n, 1) {
        pair<int, int> in = inc.get(a[i] + 1, m);
        pair<int, int> de = dec.get(1, a[i] - 1);
        if (ckmax(res, in.first + de.first + 1)) {
            tot = 1LL * in.second * de.second % MOD;
        }
        else if (in.first + de.first + 1 == res) tot = (tot + (1LL * in.second * de.second) % MOD) % MOD;
        inc.upd(a[i], make_pair(in.first + 1, in.second));
        dec.upd(a[i], make_pair(de.first + 1, de.second));
    }
    forn(i, 1, n - res) tot = (tot * 2LL) % MOD;
    cout << res << " " << tot;
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifdef DHT
        freopen("voi.inp", "r", stdin);
    #else
        //freopen("triprime.inp", "r", stdin); freopen("triprime.out", "w", stdout);
    #endif
    int tt = 1;
//    cin >> tt;
    forn(i, 1, tt) sol();
    return 0;
}

• Subtask 1: 14 / 140