Submission #735742

#	Time	Username	Problem	Language	Result	Execution time	Memory
735742		Nhoksocqt1	Zoltan (COCI16_zoltan)	C++17	140 / 140	104 ms	10896 KiB

zoltan

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
    inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
    inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 200005;
const int modl = 1000000007;

vector<int> idx;
ii dpl[MAXN], dpr[MAXN], fenl[MAXN], fenr[MAXN];
int pw2[MAXN], val[MAXN], nTree, nArr;

inline void add(int &a, const int &b) {
    if((a += b) >= modl)
        a -= modl;
}

inline void add(ii &a, const ii &b) {
    if(a.fi < b.fi)
        a = {b.fi, 0};

    if(a.fi == b.fi)
        add(a.se, b.se);
}

ii solve(int id, int cnt, int minv, int maxv) {
    if(id > nArr)
        return {cnt, 1};

    ii res = solve(id + 1, cnt, minv, maxv);
    res.se <<= 1;

    if(minv > val[id])
        add(res, solve(id + 1, 1 + cnt, val[id], maxv));

    if(maxv < val[id])
        add(res, solve(id + 1, 1 + cnt, minv, val[id]));

    return res;
}

void brute(void) {
    ii res = {0, 0};
    for (int i = 1; i <= nArr; ++i) {
        ii tmp = solve(i + 1, 1, val[i], val[i]);
        tmp.se <<= i - 1;
        add(res, tmp);
    }

    cout << res.fi << ' ' << res.se << '\n';
}

void subn5000(void) {
    ii res = {0, 0};
    for (int i = nArr; i > 0; --i) {
        dpl[i] = dpr[i] = {1, 1};
        for (int j = i + 1; j <= nArr; ++j) {
            if(val[i] > val[j])
                add(dpl[i], ii(dpl[j].fi + 1, dpl[j].se));

            if(val[i] < val[j])
                add(dpr[i], ii(dpr[j].fi + 1, dpr[j].se));
        }

        ii tmp = {dpl[i].fi + dpr[i].fi - 1, 0};
        tmp.se = 1LL * pw2[nArr - dpl[i].fi - dpr[i].fi + 1] * dpl[i].se % modl * dpr[i].se % modl;
        add(res, tmp);
    }

    cout << res.fi << ' ' << res.se << '\n';
}

void modify(bool type, int i, ii v) {
    if(type) {
        for (; i > 0; i -= i & -i)
            add(fenr[i], v);
    } else {
        for (; i <= nTree; i += i & -i)
            add(fenl[i], v);
    }
}

ii get(bool type, int i) {
    ii res = {0, 1};
    if(type) {
        for (; i <= nTree; i += i & -i)
            add(res, fenr[i]);
    } else {
        for (; i > 0; i -= i & -i)
            add(res, fenl[i]);
    }

    return res;
}

void magicFunc(void) {
    idx.clear();
    for (int i = 1; i <= nArr; ++i) {
        idx.push_back(val[i]);
    }

    sort(idx.begin(), idx.end());
    idx.erase(unique(idx.begin(), idx.end()), idx.end());

    nTree = idx.size();
    for (int i = 1; i <= nArr; ++i)
        val[i] = upper_bound(idx.begin(), idx.end(), val[i]) - idx.begin();

    ii res = {0, 0};
    for (int i = nArr; i > 0; --i) {
        dpl[i] = get(0, val[i] - 1);
        dpr[i] = get(1, val[i] + 1);

        ++dpl[i].fi, ++dpr[i].fi;
        modify(0, val[i], dpl[i]);
        modify(1, val[i], dpr[i]);

        ii tmp = {dpl[i].fi + dpr[i].fi - 1, 0};
        tmp.se = 1LL * pw2[nArr - dpl[i].fi - dpr[i].fi + 1] * dpl[i].se % modl * dpr[i].se % modl;
        add(res, tmp);
    }

    cout << res.fi << ' ' << res.se << '\n';
}

void process() {
    pw2[0] = 1;
    cin >> nArr;
    for (int i = 1; i <= nArr; ++i) {
        cin >> val[i];
        //val[i] = Random(1, 1e9); cout << val[i] << " \n"[i == nArr];
        pw2[i] = pw2[i - 1] * 2 % modl;
    }

    //brute();
    //subn5000();
    magicFunc();
}

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

    process();
    return 0;
}

• Subtask 1: 140 / 140