Submission #96796

#	Time	Username	Problem	Language	Result	Execution time	Memory
96796		tieunhi	Zoltan (COCI16_zoltan)	C++14	140 / 140	123 ms	14968 KiB

zoltan

#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 / 140