oj.uz

Submission #243543

# Submission time Handle Problem Language Result Execution time Memory
243543 2020-07-01T09:57:24 Z VEGAnn Zoltan (COCI16_zoltan) C++14
119 / 140
 125 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;

        i2 cur = {len, (ll(po[i + inv]) * ll(mex[1]) * ll(men[1])) % md};

        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:85:68: warning: narrowing conversion of '(((((ll)po[(i + inv)]) * ((ll)mex.std::array<int, 2>::operator[](1))) * ((ll)men.std::array<int, 2>::operator[](1))) % 1000000007)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
         i2 cur = {len, (ll(po[i + inv]) * ll(mex[1]) * ll(men[1])) % md};
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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 4 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 73 ms 4844 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 109 ms 5232 KB Output isn't correct
16 Incorrect 125 ms 5872 KB Output isn't correct
17 Correct 87 ms 5488 KB Output is correct
18 Correct 89 ms 5488 KB Output is correct
19 Correct 92 ms 5484 KB Output is correct
20 Correct 91 ms 5484 KB Output is correct