oj.uz

Submission #243951

# Submission time Handle Problem Language Result Execution time Memory
243951 2020-07-02T11:06:45 Z Vimmer Zoltan (COCI16_zoltan) C++14
42 / 140
 343 ms 15340 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Incorrect 6 ms 384 KB Output isn't correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Correct 5 ms 384 KB Output is correct
10 Incorrect 5 ms 384 KB Output isn't correct
11 Incorrect 187 ms 13676 KB Output isn't correct
12 Incorrect 162 ms 12912 KB Output isn't correct
13 Incorrect 150 ms 8816 KB Output isn't correct
14 Correct 223 ms 13292 KB Output is correct
15 Correct 287 ms 14448 KB Output is correct
16 Correct 343 ms 15340 KB Output is correct
17 Incorrect 242 ms 14836 KB Output isn't correct
18 Incorrect 238 ms 14832 KB Output isn't correct
19 Incorrect 242 ms 14848 KB Output isn't correct
20 Incorrect 240 ms 14720 KB Output isn't correct