oj.uz

Submission #625231

# Submission time Handle Problem Language Result Execution time Memory
625231 2022-08-09T16:30:40 Z minhi1 Zoltan (COCI16_zoltan) C++14
14 / 140
 88 ms 29020 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;
const int ninf = 0xc0c0c0c0;
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, {ninf, 0});
    }
    void upd(int i, int l, int r, int p, const 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, const 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;
pair<int, int> res = {ninf, 0};
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();
    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;
        combed(res, make_pair(in.first + de.first - 1, 1LL * in.second * de.second % 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.first) (res.second <<= 1) %= MOD;
    cout << res.first << " " << res.second;
}
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 212 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 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Correct 1 ms 212 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 46 ms 23236 KB Execution killed with signal 11
12 Runtime error 41 ms 20224 KB Execution killed with signal 11
13 Runtime error 53 ms 19180 KB Execution killed with signal 11
14 Runtime error 55 ms 20412 KB Execution killed with signal 11
15 Runtime error 67 ms 25116 KB Execution killed with signal 11
16 Runtime error 77 ms 29020 KB Execution killed with signal 11
17 Runtime error 88 ms 25060 KB Execution killed with signal 11
18 Runtime error 69 ms 25136 KB Execution killed with signal 11
19 Runtime error 56 ms 25060 KB Execution killed with signal 11
20 Runtime error 58 ms 25080 KB Execution killed with signal 11