oj.uz

Submission #229997

# Submission time Handle Problem Language Result Execution time Memory
229997 2020-05-07T15:04:57 Z osaaateiasavtnl Zoltan (COCI16_zoltan) C++14
140 / 140
 349 ms 27960 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 = 2e5 + 7, 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
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2048 KB Output is correct
2 Correct 6 ms 2048 KB Output is correct
3 Correct 6 ms 2048 KB Output is correct
4 Correct 6 ms 2048 KB Output is correct
5 Correct 7 ms 2048 KB Output is correct
6 Correct 6 ms 2048 KB Output is correct
7 Correct 7 ms 2176 KB Output is correct
8 Correct 7 ms 2304 KB Output is correct
9 Correct 8 ms 2304 KB Output is correct
10 Correct 8 ms 2304 KB Output is correct
11 Correct 179 ms 22888 KB Output is correct
12 Correct 161 ms 20200 KB Output is correct
13 Correct 143 ms 19056 KB Output is correct
14 Correct 228 ms 20328 KB Output is correct
15 Correct 300 ms 24552 KB Output is correct
16 Correct 349 ms 27960 KB Output is correct
17 Correct 225 ms 25556 KB Output is correct
18 Correct 225 ms 25564 KB Output is correct
19 Correct 219 ms 25576 KB Output is correct
20 Correct 215 ms 25448 KB Output is correct