oj.uz

Submission #625235

# Submission time Handle Problem Language Result Execution time Memory
625235 2022-08-09T16:39:59 Z minhi1 Zoltan (COCI16_zoltan) C++14
14 / 140
 76 ms 29156 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> operator | (const pair<int, int> &x, const pair<int, int> &y) {
    if (x.first == y.first) return make_pair(x.first, (x.second + y.second) % MOD);
    return max(x, y);
}
void operator |= (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) {
            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] = 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 {ninf, 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 L | R;
    }
    pair<int, int> get(int u, int v) {
        return get(1, 1, n, u, v) | make_pair(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;
        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 1 ms 212 KB Output isn't correct
4 Correct 0 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 41 ms 20292 KB Execution killed with signal 11
13 Runtime error 41 ms 19144 KB Execution killed with signal 11
14 Runtime error 64 ms 20420 KB Execution killed with signal 11
15 Runtime error 74 ms 25220 KB Execution killed with signal 11
16 Runtime error 76 ms 29156 KB Execution killed with signal 11
17 Runtime error 60 ms 25076 KB Execution killed with signal 11
18 Runtime error 60 ms 25032 KB Execution killed with signal 11
19 Runtime error 61 ms 25100 KB Execution killed with signal 11
20 Runtime error 69 ms 25060 KB Execution killed with signal 11