oj.uz

답안 #243966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243966 2020-07-02T12:10:37 Z Vimmer Zoltan (COCI16_zoltan) C++14
112 / 140
 141 ms 16104 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 300101
#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;


ll a[N], n;

pair <ll, ll> fl[N], fr[N], L[N], R[N];


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

void updr(ll x, pair <ll, ll> val)
{
    x += 5;

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

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

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

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

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

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

    return ans;
}

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

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

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

    return ans;
}


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

    ll 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 <ll> pr; pr.clear();

    for (ll 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 (ll i = 0; i < n; i++) {a[i] = lower_bound(pr.begin(), pr.end(), a[i]) - pr.begin();}

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

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

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

        L[v] = valer;

        valer.F++;

        updl(v, valer);
    }

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

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

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

        R[v] = valer;

        valer.F++;

        updr(v, valer);
    }

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

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

        ll len = L[v].F + R[v].F + 1;

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

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

        upd(ans, pre);
    }

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

Subtask #1
112.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 79 ms 12904 KB Output is correct
12 Correct 68 ms 11376 KB Output is correct
13 Correct 65 ms 10632 KB Output is correct
14 Correct 95 ms 11368 KB Output is correct
15 Correct 119 ms 13928 KB Output is correct
16 Correct 141 ms 16104 KB Output is correct
17 Incorrect 116 ms 14184 KB Output isn't correct
18 Incorrect 105 ms 14332 KB Output isn't correct
19 Incorrect 100 ms 14312 KB Output isn't correct
20 Incorrect 96 ms 14188 KB Output isn't correct