oj.uz

Submission #243523

# Submission time Handle Problem Language Result Execution time Memory
243523 2020-07-01T09:34:53 Z VEGAnn Zoltan (COCI16_zoltan) C++14
140 / 140
 388 ms 11096 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define i2 array<int,2>
#define PB push_back
using namespace std;
const int N = 200100;
const int oo = 2e9;
const int md = int(1e9) + 7;
i2 ans, st[2][4 * N];
vector<int> vc;
int n, a[N], po[N];

int mult(int x, int y) { return (1ll * x * y) % md; }

void SUM(int &x, int y){
    x += y;
    if (x >= md)
        x -= md;
}

void upd(i2 &cr, i2 nw){
    if (nw[0] > cr[0])
        cr = nw; else
    if (nw[0] == cr[0]){
        SUM(cr[1], nw[1]);
    }
}

i2 get(int tp, int v, int tl, int tr, int l, int r){
    if (l > r) return {0, 0};

    if (tl == l && tr == r) return st[tp][v];

    int md = (tl + tr) >> 1;

    i2 res = get(tp, v + v, tl, md, l, min(r, md));
    upd(res, get(tp, v + v + 1, md + 1, tr, max(md + 1, l), r));

    return res;
}

void update(int tp, int v, int l, int r, int ps, i2 vl){
    if (l == r){
        upd(st[tp][v], vl);
        return;
    }

    int md = (l + r) >> 1;

    if (ps <= md)
        update(tp, v + v, l, md, ps, vl);
    else update(tp, v + v + 1, md + 1 ,r, ps, vl);

    st[tp][v] = st[tp][v + v];
    upd(st[tp][v], st[tp][v + v + 1]);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        vc.PB(a[i]);
    }

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < n; i++)
        a[i] = lower_bound(all(vc), a[i]) - vc.begin();

    po[0] = 1;

    for (int i = 1; i <= n; i++)
        po[i] = (po[i - 1] * 2) % md;

    for (int i = n - 1; i >= 0; i--){
        i2 men = get(0, 1, 0, sz(vc) - 1, 0, a[i] - 1);
        i2 mex = get(1, 1, 0, sz(vc) - 1, a[i] + 1, sz(vc) - 1);

        if (men[0] == 0)
            men[1] = 1;

        if (mex[0] == 0)
            mex[1] = 1;

        int len = men[0] + mex[0] + 1;
        int inv = (n - i) - len;

        i2 cur = {len, mult(po[i + inv], mult(mex[1], men[1]))};

        upd(ans, cur);

//        cerr << ans[0] << " " << ans[1] << '\n';

        men[0]++;
        mex[0]++;

        update(0, 1, 0, sz(vc) - 1, a[i], men);
        update(1, 1, 0, sz(vc) - 1, a[i], mex);
    }

    cout << ans[0] << " " << ans[1];

    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 213 ms 10584 KB Output is correct
12 Correct 183 ms 10316 KB Output is correct
13 Correct 179 ms 6116 KB Output is correct
14 Correct 246 ms 10324 KB Output is correct
15 Correct 323 ms 10712 KB Output is correct
16 Correct 388 ms 10988 KB Output is correct
17 Correct 288 ms 11096 KB Output is correct
18 Correct 283 ms 10988 KB Output is correct
19 Correct 270 ms 10992 KB Output is correct
20 Correct 273 ms 10988 KB Output is correct