oj.uz

Submission #243537

# Submission time Handle Problem Language Result Execution time Memory
243537 2020-07-01T09:52:20 Z VEGAnn Zoltan (COCI16_zoltan) C++14
63 / 140
 129 ms 5920 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])) % 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 5 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 5 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 76 ms 4848 KB Output is correct
12 Correct 64 ms 4208 KB Output is correct
13 Correct 60 ms 4084 KB Output is correct
14 Incorrect 86 ms 4212 KB Output isn't correct
15 Incorrect 110 ms 5232 KB Output isn't correct
16 Incorrect 129 ms 5920 KB Output isn't correct
17 Incorrect 91 ms 5484 KB Output isn't correct
18 Incorrect 88 ms 5492 KB Output isn't correct
19 Incorrect 91 ms 5488 KB Output isn't correct
20 Incorrect 89 ms 5488 KB Output isn't correct