Submission #996875

#	Time	Username	Problem	Language	Result	Execution time	Memory
996875		otarius	Zoltan (COCI16_zoltan)	C++17	21 / 140	243 ms	23992 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define sc second
#define int long long
#define ll long long
#define pii pair<int, int>
#define pb push_back
const ll mod = 1e9 + 9;
const ll inf = 1e9 + 7;
pii inc[800040], der[800040];
pii getinc(int v, int tl, int tr, int l, int r) {
    if (l > r) return {0, 1};
    if (tl == l && tr == r) {
        return inc[v];
    }
    int tm = (tl + tr) / 2;
    pii x = getinc(2 * v, tl, tm, l, min(r, tm));
    pii y = getinc(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
    if (x.ff == y.ff) return {x.ff, (x.sc + y.sc) % inf};
    return max(x, y);
}
pii getder(int v, int tl, int tr, int l, int r) {
    if (l > r) return {0, 1};
    if (tl == l && tr == r)
        return der[v];
    int tm = (tl + tr) / 2;
    pii x = getder(2 * v, tl, tm, l, min(r, tm));
    pii y = getder(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
    if (x.ff == y.ff) return {x.ff, (x.sc + y.sc) % inf};
    else if (x.ff > y.ff) return x;
    else return y;
}
void updinc(int v, int tl, int tr, int pos, pii val) {
    if (tl == tr) {
        inc[v] = val;
        return;
    } int tm = (tl + tr) / 2;
    if (pos <= tm) updinc(2 * v, tl, tm, pos, val);
    else updinc(2 * v + 1, tm + 1, tr, pos, val); 
    if (inc[2 * v].ff == inc[2 * v + 1].ff) inc[v] = {inc[2 * v].ff, (inc[2 * v].sc + inc[2 * v + 1].sc) % inf};
    else inc[v] = max(inc[2 * v], inc[2 * v + 1]);
}
void updder(int v, int tl, int tr, int pos, pii val) {
    if (tl == tr) {
        der[v] = val;
        return;
    } int tm = (tl + tr) / 2;
    if (pos <= tm) updder(2 * v, tl, tm, pos, val);
    else updder(2 * v + 1, tm + 1, tr, pos, val);
    if (der[2 * v].ff == der[2 * v + 1].ff) der[v] = {der[2 * v].ff, (der[2 * v].sc + der[2 * v + 1].sc) % inf};
    else der[v] = max(der[2 * v], der[2 * v + 1]);
}
ll binpow(ll a, ll b) {
    a %= inf;
    if (!b) return 1;
    if (b & 1) return a * binpow(a, b - 1) % inf;
    return binpow(a * a, b >> 1) % inf;
}
void solve() {
    int n;
    cin >> n;
    vector<int> v;
    int arr[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> arr[i]; v.pb(arr[i]);
    } sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    for (int i = 1; i <= n; i++)
        arr[i] = lower_bound(v.begin(), v.end(), arr[i]) - v.begin() + 1;
    pii ans = {0, 0};
    for (int i = n; i >= 1; i--) {
        pii up = getinc(1, 1, n, arr[i] + 1, n);
        pii dw = getder(1, 1, n, 1, arr[i] - 1);
        up.ff++; dw.ff++;
        up.sc = max(up.sc, 1LL); dw.sc = max(dw.sc, 1LL);
        pii now = {up.ff + dw.ff - 1, (up.sc * dw.sc) % inf};
        if (now.ff == ans.ff) ans.sc += now.sc;
        else if (now.ff > ans.ff) ans = now;
        updinc(1, 1, n, arr[i], up);
        updder(1, 1, n, arr[i], dw);
    } cout << ans.ff << ' ' << (ans.sc * binpow(2, n - ans.ff)) % inf;
    
}
int32_t main() {
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
        cout << endl;
    }
}

• Subtask 1: 21 / 140