oj.uz

Submission #625226

# Submission time Handle Problem Language Result Execution time Memory
625226 2022-08-09T16:22:38 Z minhi1 Zoltan (COCI16_zoltan) C++14
14 / 140
 68 ms 16472 KB 
#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(2 * 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);
        ++in.first; ++de.first;
        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, in.second));
        dec.upd(a[i], make_pair(de.first, 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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Correct 0 ms 212 KB Output is correct
7 Runtime error 1 ms 468 KB Execution killed with signal 11
8 Runtime error 1 ms 468 KB Execution killed with signal 11
9 Runtime error 1 ms 468 KB Execution killed with signal 11
10 Runtime error 1 ms 468 KB Execution killed with signal 11
11 Runtime error 40 ms 13188 KB Execution killed with signal 11
12 Runtime error 35 ms 11528 KB Execution killed with signal 11
13 Runtime error 33 ms 10976 KB Execution killed with signal 11
14 Runtime error 45 ms 11700 KB Execution killed with signal 11
15 Runtime error 58 ms 14320 KB Execution killed with signal 11
16 Runtime error 68 ms 16472 KB Execution killed with signal 11
17 Runtime error 51 ms 14520 KB Execution killed with signal 11
18 Runtime error 52 ms 14460 KB Execution killed with signal 11
19 Runtime error 50 ms 14436 KB Execution killed with signal 11
20 Runtime error 50 ms 14476 KB Execution killed with signal 11