Submission #243951

#	Time	Username	Problem	Language	Result	Execution time	Memory
243951		Vimmer	Zoltan (COCI16_zoltan)	C++14	42 / 140	343 ms	15340 KiB

zoltan

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 200101
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 2> a2;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


int a[N], n;

pair <int, int> fl[N], fr[N], pshl[N * 4], pshr[N * 4];

void bld(int v, int tl, int tr)
{
    pshl[v] = pshr[v] = {-1, -1};

    if (tl == tr)
    {
        fl[tl] = {1, 1};

        fr[tl] = {1, 1};

        return;
    }

    int md = (tl + tr) >> 1;

    bld(v + v, tl, md); bld(v + v + 1, md + 1, tr);
}

void upd(pair <int, int> &a, pair <int, int> &b) {if (a.F == b.F) a.S = (a.S + b.S) % M; else if (a.F < b.F) a = b;}

void Pushl(int v, int tl, int tr)
{
    if (pshl[v].F == -1) return;

    if (tl == tr) upd(fl[tl], pshl[v]);
    else
    {
        upd(pshl[v + v], pshl[v]);

        upd(pshl[v + v + 1], pshl[v]);
    }

    pshl[v] = {-1, -1};
}

void Pushr(int v, int tl, int tr)
{
    if (pshr[v].F == -1) return;

    if (tl == tr) upd(fr[tl], pshr[v]);
    else
    {
        upd(pshr[v + v], pshr[v]);

        upd(pshr[v + v + 1], pshr[v]);
    }

    pshr[v] = {-1, -1};
}

void updl(int v, int tl, int tr, int l, int r, pair <int, int> val)
{
    if (r < tl || tr < l || l > r || tl > tr) return;

    Pushl(v, tl, tr);

    if (l <= tl && tr <= r)
    {
        upd(pshl[v], val);

        Pushl(v, tl, tr);

        return;
    }

    int md = (tl + tr) >> 1;

    updl(v + v, tl, md, l, r, val); updl(v + v + 1, md + 1, tr, l, r, val);
}

void updr(int v, int tl, int tr, int l, int r, pair <int, int> val)
{
    if (r < tl || tr < l || l > r || tl > tr) return;

    Pushr(v, tl, tr);

    if (l <= tl && tr <= r)
    {
        upd(pshr[v], val);

        Pushr(v, tl, tr);

        return;
    }

    int md = (tl + tr) >> 1;

    updr(v + v, tl, md, l, r, val); updr(v + v + 1, md + 1, tr, l, r, val);
}

void gtl(int v, int tl, int tr, int pos)
{
    Pushl(v, tl, tr);

    if (tl == tr) return;

    int md = (tl + tr) >> 1;

    if (pos <= md) gtl(v + v, tl, md, pos);
      else gtl(v + v + 1, md + 1, tr, pos);
}

void gtr(int v, int tl, int tr, int pos)
{
    Pushr(v, tl, tr);

    if (tl == tr) return;

    int md = (tl + tr) >> 1;

    if (pos <= md) gtr(v + v, tl, md, pos);
      else gtr(v + v + 1, md + 1, tr, pos);
}

int binpow(int a, int b)
{
    if (b == 0) return 1;

    int s = binpow(a, b / 2);

    s = (ll(s) * ll(s)) % M;

    if (b % 2) s = (ll(s) * ll(a)) % M;

    return s;
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    vector <int> pr; pr.clear();

    for (int i = 0; i < n; i++) {cin >> a[i]; pr.pb(a[i]);}

    sort(pr.begin(), pr.end());

    pr.resize(unique(pr.begin(), pr.end()) - pr.begin());

    for (int i = 0; i < n; i++) a[i] = lower_bound(pr.begin(), pr.end(), a[i]) - pr.begin();

    bld(1, 0, n - 1);

    for (int i = n - 1; i >= 0; i--)
    {
        gtl(1, 0, n - 1, a[i]);

        updl(1, 0, n - 1, a[i] + 1, n - 1, {fl[a[i]].F + 1, fl[a[i]].S});
    }

    for (int i = n - 1; i >= 0; i--)
    {
        gtr(1, 0, n - 1, a[i]);

        updr(1, 0, n - 1, 0, a[i] - 1, {fr[a[i]].F + 1, fr[a[i]].S});
    }

    pair <int, int> ans = {-1, -1};

    for (int i = 0; i < n; i++)
    {
        int v = a[i];

        int len = fl[v].F + fr[v].F - 1;

        int val = (ll(fl[v].S) * ll(fr[v].S)) % M;

        if (ans.F < len) ans = {len, val};
         else if (ans.F == len) ans.S = (ll(ans.S) * ll(val)) % M;
    }

    cout << ans.F << " " << (ll(ans.S) * ll(binpow(2, n - ans.F))) % M << endl;
}

• Subtask 1: 42 / 140