oj.uz

Submission #625229

# Submission time Handle Problem Language Result Execution time Memory
625229 2022-08-09T16:27:46 Z minhi1 Zoltan (COCI16_zoltan) C++14
14 / 140
 78 ms 29148 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;
pair<int, int> res = {-1, 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 0 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 1 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Correct 0 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 48 ms 23248 KB Execution killed with signal 11
12 Runtime error 39 ms 20228 KB Execution killed with signal 11
13 Runtime error 37 ms 19216 KB Execution killed with signal 11
14 Runtime error 52 ms 20392 KB Execution killed with signal 11
15 Runtime error 63 ms 25220 KB Execution killed with signal 11
16 Runtime error 78 ms 29148 KB Execution killed with signal 11
17 Runtime error 57 ms 25068 KB Execution killed with signal 11
18 Runtime error 56 ms 25072 KB Execution killed with signal 11
19 Runtime error 56 ms 25152 KB Execution killed with signal 11
20 Runtime error 57 ms 25092 KB Execution killed with signal 11