oj.uz

Submission #96796

# Submission time Handle Problem Language Result Execution time Memory
96796 2019-02-12T03:23:59 Z tieunhi Zoltan (COCI16_zoltan) C++14
140 / 140
 123 ms 14968 KB 
#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define pii pair<int, int>
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define N 1000005
#define BASE 97
#define mod 1000000007
#define mid (r + l)/2

using namespace std;

int n, a[N], rr[N], cur;
int A[N], B[N], numA[N], numB[N];

void inline add(int &A, int B) {A += B; if (A >= mod) A -= mod;}
int inline mul(int A, int B) {return (1ll*A*B) % mod;}
int Pow(int A, int B)
{
    if (B == 0) return 1;
    int X = Pow(A, B/2);
    X = mul(X, X);
    if (B % 2) X = mul(X, A);
    return X;
}

void setup()
{
    cin >> n;
    FOR(i, 1, n) cin >> a[i], rr[i] = a[i];
    sort(rr+1, rr+n+1);
    cur = unique(rr+1, rr+n+1) - rr - 1;
    FOR(i, 1, n)
        a[i] = lower_bound(rr+1, rr+cur+1, a[i]) - rr;
}
struct BIT
{
    int t[N], num[N];
    void reset()
    {
        memset(t, 0, sizeof t);
        memset(num, 0, sizeof num);
    }
    void upd(int x, int val, int val2)
    {
        for (; x < N; x += (x & -x))
        {
            if (val > t[x]) t[x] = val, num[x] = val2;
            else if (val == t[x]) add(num[x], val2);
        }
    }
    pii get(int x)
    {
        int ans = 0, ans2 = 1;
        for (; x; x -= (x & -x))
        {
            if (t[x] > ans) ans = t[x], ans2 = num[x];
            else if (t[x] == ans) add(ans2, num[x]);
        }
        return mp(ans, ans2);
    }
}t;
void prepare()
{
    t.upd(a[n], 1, 1);
    A[n] = numA[n] = B[n] = numB[n] = 1;
    FORD(i, n-1, 1)
    {
        pii z = t.get(a[i]-1);
        t.upd(a[i], z.F+1, z.S);
        A[i] = z.F+1;
        numA[i] = z.S;
    }
    t.reset();
    FOR(i, 1, n) a[i] = cur - a[i] + 1;
    t.upd(a[n], 1, 1);
    FORD(i, n-1, 1)
    {
        pii z = t.get(a[i]-1);
        t.upd(a[i], z.F+1, z.S);
        B[i] = z.F+1;
        numB[i] = z.S;
    }
}
void solve()
{
    int lenMax = 0;
    FOR(i, 1, n) lenMax = max(lenMax, A[i] + B[i] - 1);
    int res = 0;
    FOR(i, 1, n)
        if (A[i] + B[i] - 1 == lenMax)
            add(res, mul(mul(numA[i], numB[i]), Pow(2, n - lenMax)));
    cout <<lenMax<<' '<<res;
}
int main()
{
    ios_base::sync_with_stdio(0); cout.tie(0);
   // freopen("INP.TXT", "r", stdin);
    //freopen("OUT.TXT", "w", stdout);
    setup();
    prepare();
    solve();
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8312 KB Output is correct
2 Correct 9 ms 8188 KB Output is correct
3 Correct 7 ms 8184 KB Output is correct
4 Correct 7 ms 8204 KB Output is correct
5 Correct 8 ms 8184 KB Output is correct
6 Correct 7 ms 8184 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Correct 8 ms 8312 KB Output is correct
9 Correct 10 ms 8184 KB Output is correct
10 Correct 8 ms 8312 KB Output is correct
11 Correct 70 ms 13176 KB Output is correct
12 Correct 67 ms 12536 KB Output is correct
13 Correct 58 ms 12284 KB Output is correct
14 Correct 84 ms 12764 KB Output is correct
15 Correct 110 ms 13896 KB Output is correct
16 Correct 123 ms 14968 KB Output is correct
17 Correct 89 ms 14200 KB Output is correct
18 Correct 95 ms 14168 KB Output is correct
19 Correct 90 ms 14200 KB Output is correct
20 Correct 96 ms 14200 KB Output is correct