oj.uz

Submission #229996

# Submission time Handle Problem Language Result Execution time Memory
229996 2020-05-07T15:04:35 Z osaaateiasavtnl Zoltan (COCI16_zoltan) C++14
42 / 140
 6 ms 512 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 107, MOD = 1000 * 1000 * 1000 + 7;
int a[N], l[N], r[N], cntl[N], cntr[N], pw[N];

struct Seg {

ii tree[N << 2];
ii merge(ii a, ii b) {
    if (a.f > b.f)
        return a;
    if (b.f > a.f)
        return b;
    return mp(a.f, (a.s + b.s) % MOD);
}   
void add(int v, int l, int r, int i, ii e) {
    if (l == r) {
        tree[v] = merge(tree[v], e);
        return;
    }   
    int m = (l + r) >> 1;
    if (i <= m)
        add(v * 2 + 1, l, m, i, e);
    else
        add(v * 2 + 2, m + 1, r, i, e);
    tree[v] = merge(tree[v * 2 + 1], tree[v * 2 + 2]);                   
}   
ii get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl)
        return mp(0, 0);
    if (l <= tl && tr <= r) {
        //cout << tl << ' ' << tr << " : " << tree[v].f << ' ' << tree[v].s << endl;
        return tree[v];
    }              
    int m = (tl + tr) >> 1;
    return merge(get(v * 2 + 1, tl, m, l, r), get(v * 2 + 2, m + 1, tr, l, r));
}   

} L, R;  

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    pw[0] = 1;
    for (int i = 1; i < N; ++i)
        pw[i] = (pw[i - 1] * 2) % MOD;

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector <int> c;
    for (int i = 1; i <= n; ++i)
        c.app(a[i]);
    sort(all(c));
    c.resize(unique(all(c)) - c.begin());
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(all(c), a[i]) - c.begin();

    int len = 0;
    for (int i = n; i; --i) {
        tie(l[i], cntl[i]) = L.get(0, 0, N, 0, a[i] - 1);
        ++l[i];

        //cout << i << ' ' << l[i] << ' ' << cntl[i] << endl;

        if (l[i] == 1)
            cntl[i] = 1;

        tie(r[i], cntr[i]) = R.get(0, 0, N, a[i] + 1, N);
        ++r[i];
        if (r[i] == 1)
            cntr[i] = 1;
        
        L.add(0, 0, N, a[i], mp(l[i], cntl[i]));
        R.add(0, 0, N, a[i], mp(r[i], cntr[i]));
        len = max(len, l[i] + r[i] - 1);
    }   

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (l[i] + r[i] - 1 == len) {
            ans += (cntl[i] * cntr[i]) % MOD;
            ans %= MOD;
        }   
    }
    ans = ans * pw[n - len] % MOD;

    cout << len << ' ' << ans << endl;
}

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 6 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)