Submission #1033392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033392		raphaelp	Zoltan (COCI16_zoltan)	C++14	112 / 140	309 ms	13904 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
int MOD = 1000000007;
class SegTree
{
private:
    vector<int> st, count;
    int N;
    int l(int x) { return (x << 1); }
    int r(int x) { return (x << 1) + 1; }
    void update(int L, int R, int a, int val, int c, int x)
    {
        if (L > a || R < a)
            return;
        if (L == a && R == a)
        {
            if (val > st[x])
            {
                st[x] = val;
                count[x] = 0;
            }
            if (val == st[x])
            {
                count[x] += c;
                count[x] = count[x] % MOD;
            }
        }
        else
        {
            int m = (L + R) / 2;
            update(L, m, a, val, c, l(x));
            update(m + 1, R, a, val, c, r(x));
            st[x] = max(st[l(x)], st[r(x)]);
            count[x] = ((st[l(x)] == st[x]) ? count[l(x)] : 0) + ((st[r(x)] == st[x]) ? count[r(x)] : 0);
            count[x] = count[x] % MOD;
        }
    }
    pair<int, int> RSQ(int L, int R, int a, int b, int x)
    {
        if (L > b || R < a)
            return {0, 0};
        if (L >= a && R <= b)
            return {st[x], count[x]};
        int m = (L + R) / 2;
        pair<int, int> temp1 = RSQ(L, m, a, b, l(x)), temp2 = RSQ(m + 1, R, a, b, r(x));
        if (temp1.first < temp2.first)
            swap(temp1, temp2);
        if (temp1.first == temp2.first)
            temp1.second += temp2.second;
        temp1.second = temp1.second % MOD;
        return temp1;
    }

public:
    SegTree(int x)
    {
        N = pow(2, ceil(log2(x)));
        st.assign(2 * N, 0);
        count.assign(2 * N, 0);
    }
    void update(int x, int val, int c) { update(0, N - 1, x, val, c, 1); }
    pair<int, int> RSQ(int a, int b) { return RSQ(0, N - 1, a, b, 1); }
};
int main()
{
    int N;
    cin >> N;
    vector<int> Tab(N), vals(N);
    for (int i = 0; i < N; i++)
    {
        cin >> Tab[i];
        vals[i] = Tab[i];
    }
    sort(vals.begin(), vals.end());
    map<int, int> M;
    int buff = 1;
    for (int i = 0; i < N; i++)
    {
        M[vals[i]] = buff++;
    }
    for (int i = 0; i < N; i++)
        Tab[i] = M[Tab[i]];
    M.clear();
    vals.clear();
    vector<pair<int, int>> ansleft(N), ansright(N);
    SegTree STL(N + 1), STR(N + 1);
    int best = 0;
    for (int i = N - 1; i >= 0; i--)
    {
        ansleft[i] = STL.RSQ(0, Tab[i] - 1);
        ansright[i] = STR.RSQ(Tab[i] + 1, N);
        ansleft[i].first++, ansright[i].first++;
        if (ansleft[i].first == 1)
            ansleft[i].second++;
        if (ansright[i].first == 1)
            ansright[i].second++;
        ansleft[i].second = ansleft[i].second % MOD;
        ansright[i].second = ansright[i].second % MOD;
        STL.update(Tab[i], ansleft[i].first, ansleft[i].second);
        STR.update(Tab[i], ansright[i].first, ansright[i].second);
        best = max(best, ansright[i].first + ansleft[i].first);
    }
    long long tot = 0;
    for (int i = 0; i < N; i++)
    {
        if (ansright[i].first + ansleft[i].first == best)
            tot = (long long)(tot + (long long)(ansright[i].second * ansleft[i].second)) % MOD;
    }
    for (int i = 0; i < N - best + 1; i++)
    {
        tot = (tot * 2) % MOD;
    }
    cout << best - 1 << ' ' << tot;
}

• Subtask 1: 112 / 140