oj.uz

Submission #243540

# Submission time Handle Problem Language Result Execution time Memory
243540 2020-07-01T09:55:28 Z VEGAnn Zoltan (COCI16_zoltan) C++14
119 / 140
 134 ms 5872 KB 
#include <bits/stdc++.h>
#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;
typedef long long ll;
const int N = 200100;
const int oo = 2e9;
const int md = int(1e9) + 7;
i2 ans, st[2][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){
    i2 res = {0, 0};

    for (; v >= 0; v = (v & (v + 1)) - 1)
        upd(res, st[tp][v]);

    return res;
}

void update(int tp, int v, i2 vl){
    for (; v < sz(vc); v = (v | (v + 1)))
        upd(st[tp][v], vl);
}

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];
        SUM(po[i], po[i - 1]);
    }

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

        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;

        ll cnt = (ll(po[i + inv]) * ll(mex[1]) * ll(men[1])) % md;

        i2 cur = {len, cnt};

        upd(ans, cur);

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

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

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

    return 0;
}

Compilation message

zoltan.cpp: In function 'int main()':
zoltan.cpp:87:27: warning: narrowing conversion of 'cnt' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
         i2 cur = {len, cnt};
                           ^

Subtask #1
119.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 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 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 79 ms 4848 KB Output is correct
12 Correct 66 ms 4236 KB Output is correct
13 Correct 60 ms 4084 KB Output is correct
14 Incorrect 89 ms 4208 KB Output isn't correct
15 Incorrect 111 ms 5232 KB Output isn't correct
16 Incorrect 134 ms 5872 KB Output isn't correct
17 Correct 94 ms 5432 KB Output is correct
18 Correct 93 ms 5488 KB Output is correct
19 Correct 89 ms 5488 KB Output is correct
20 Correct 88 ms 5484 KB Output is correct