Submission #243961

#	Time	Username	Problem	Language	Result	Execution time	Memory
243961		Vimmer	Zoltan (COCI16_zoltan)	C++14	126 / 140	130 ms	8432 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 pair <int, int> par;
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], L[N], R[N];


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 updr(int x, pair <int, int> val)
{
    x += 5;

    for (; x >= 0; x = (x & (x + 1)) - 1) upd(fr[x], val);
}

void updl(int x, pair <int, int> val)
{
    x += 5;

    for (; x < N; x = (x | (x + 1))) upd(fl[x], val);
}

pair <int, int> gtl(int x)
{
    x += 5;

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

    for (; x >= 0; x = (x & (x + 1)) - 1) upd(ans, fl[x]);

    return ans;
}

pair <int, int> gtr(int x)
{
    x += 5;

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

    for (; x < N; x = (x | (x + 1))) upd(ans, fr[x]);

    return ans;
}


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();}

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

        pair <int, int> valer = gtl(v - 1);

        if (valer.F == 0) valer.S = 1;

        L[v] = valer;

        valer.F++;

        updl(v, valer);
    }

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

        pair <int, int> valer = gtr(v + 1);

        if (valer.F == 0) valer.S = 1;

        R[v] = valer;

        valer.F++;

        updr(v, valer);
    }

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

    for (int i = 0; i < n; i++)
    {
        int len = L[i].F + R[i].F + 1;

        int val = (ll(L[i].S) * ll(R[i].S)) % M;

        pair <int, int> pre = {len, val};

        upd(ans, pre);
    }

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

• Subtask 1: 126 / 140