oj.uz

Submission #243536

# Submission time Handle Problem Language Result Execution time Memory
243536 2020-07-01T09:51:34 Z VEGAnn Zoltan (COCI16_zoltan) C++14
63 / 140
 128 ms 6000 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 = (1ll * po[i + inv] * mex[1]) % md;

        (cnt *= 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:25: warning: value computed is not used [-Wunused-value]
         (cnt *= men[1]) % md;
         ~~~~~~~~~~~~~~~~^~~~
zoltan.cpp:89:27: warning: narrowing conversion of 'cnt' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
         i2 cur = {len, cnt};
                           ^

Subtask #1
63.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 4 ms 384 KB Output is correct
4 Correct 4 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 Incorrect 5 ms 384 KB Output isn't correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Incorrect 5 ms 384 KB Output isn't correct
11 Correct 75 ms 4844 KB Output is correct
12 Correct 68 ms 4208 KB Output is correct
13 Correct 61 ms 4084 KB Output is correct
14 Incorrect 88 ms 4336 KB Output isn't correct
15 Incorrect 108 ms 5232 KB Output isn't correct
16 Incorrect 128 ms 6000 KB Output isn't correct
17 Incorrect 91 ms 5488 KB Output isn't correct
18 Incorrect 91 ms 5488 KB Output isn't correct
19 Incorrect 92 ms 5484 KB Output isn't correct
20 Incorrect 89 ms 5488 KB Output isn't correct