oj.uz

Submission #625218

# Submission time Handle Problem Language Result Execution time Memory
625218 2022-08-09T16:16:39 Z minhi1 Zoltan (COCI16_zoltan) C++14
14 / 140
 75 ms 30940 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(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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Correct 1 ms 328 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Correct 0 ms 340 KB Output is correct
7 Runtime error 1 ms 596 KB Execution killed with signal 11
8 Runtime error 1 ms 596 KB Execution killed with signal 11
9 Runtime error 1 ms 596 KB Execution killed with signal 11
10 Runtime error 1 ms 596 KB Execution killed with signal 11
11 Runtime error 47 ms 24452 KB Execution killed with signal 11
12 Runtime error 44 ms 21428 KB Execution killed with signal 11
13 Runtime error 38 ms 20144 KB Execution killed with signal 11
14 Runtime error 62 ms 21688 KB Execution killed with signal 11
15 Runtime error 63 ms 26788 KB Execution killed with signal 11
16 Runtime error 75 ms 30940 KB Execution killed with signal 11
17 Runtime error 59 ms 26312 KB Execution killed with signal 11
18 Runtime error 69 ms 26300 KB Execution killed with signal 11
19 Runtime error 59 ms 26440 KB Execution killed with signal 11
20 Runtime error 60 ms 26388 KB Execution killed with signal 11