Submission #202052

#	Time	Username	Problem	Language	Result	Execution time	Memory
202052		SamAnd	Zoltan (COCI16_zoltan)	C++17	140 / 140	575 ms	28520 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 200005, M = 1000000007;

int n;
int a[N];
int ast[N];

pair<int, int> t[N * 4][2];

pair<int, int> mer(const pair<int, int>& l, const pair<int, int>& r)
{
    if (l.first > r.first)
        return l;
    if (l.first < r.first)
        return r;
    return m_p(l.first, (l.second + r.second) % M);
}

void ubd(int tl, int tr, int x, pair<int, int> y, int z, int pos)
{
    if (tl == tr)
    {
        if (y.first > t[pos][z].first)
        {
            t[pos][z] = y;
        }
        else if (y.first == t[pos][z].first)
        {
            t[pos][z].second = (t[pos][z].second + y.second) % M;
        }
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, z, pos * 2);
    else
        ubd(m + 1, tr, x, y, z, pos * 2 + 1);
    t[pos][z] = mer(t[pos * 2][z], t[pos * 2 + 1][z]);
}

pair<int, int> qry(int tl, int tr, int l, int r, int z, int pos)
{
    if (l > r)
        return m_p(0, 0);
    if (tl == l && tr == r)
        return t[pos][z];
    int m = (tl + tr) / 2;
    return mer(qry(tl, m, l, min(m, r), z, pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, z, pos * 2 + 1));
}

pair<int, int> ans[N * 2][2];

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int z = 0;
    vector<int> v;
    map<int, int> mp;
    for (int i = 1; i <= n; ++i)
        v.push_back(a[i]);
    sort(v.begin(), v.end());
    for (int i = 0; i < n; ++i)
    {
        if (!i || v[i] != v[i - 1])
            mp[v[i]] = ++z;
    }
    for (int i = 1; i <= n; ++i)
        a[i] = mp[a[i]];
    ast[0] = 1;
    for (int i = 1; i <= n; ++i)
        ast[i] = (ast[i - 1] * 2) % M;
    //////////////////////////////////////////////
    for (int i = n; i > 1; --i)
    {
        ans[n - i + 1][0] = qry(1, z, 1, a[i] - 1, 0, 1);
        if (ans[n - i + 1][0].second)
            ++ans[n - i + 1][0].first;
        ans[n - i + 1][0] = mer(ans[n - i + 1][0], m_p(1, 1));
        ubd(1, z, a[i], ans[n - i + 1][0], 0, 1);
    }
    ans[n][1] = qry(1, z, 1, a[1] - 1, 0, 1);
    if (ans[n][1].second)
        ++ans[n][1].first;
    ans[n][1] = mer(ans[n][1], m_p(1, 1));
    ubd(1, z, a[1], ans[n][1], 1, 1);
    for (int i = 2; i <= n; ++i)
    {
        ans[n + i - 1][0] = qry(1, z, 1, a[i] - 1, 0, 1);
        if (ans[n + i - 1][0].second)
            ++ans[n + i - 1][0].first;
        ans[n + i - 1][0] = mer(ans[n + i - 1][0], m_p(1, 1));
        ubd(1, z, a[i], ans[n + i - 1][0], 0, 1);
        ans[n + i - 1][1] = qry(1, z, 1, a[i] - 1, 1, 1);
        if (ans[n + i - 1][1].second)
            ++ans[n + i - 1][1].first;
        ubd(1, z, a[i], ans[n + i - 1][1], 1, 1);
    }
    pair<int, int> yans[2] = {};
    for (int i = 1; i < n * 2; ++i)
    {
        yans[1] = mer(yans[1], ans[i][1]);
        yans[0] = mer(yans[0], ans[i][0]);
    }
    yans[0].second = (yans[0].second * 1LL * ast[n - yans[0].first - 1]) % M;
    yans[1].second = (yans[1].second * 1LL * ast[n - yans[1].first]) % M;
    yans[0] = mer(yans[0], yans[1]);
    printf("%d %d\n", yans[0].first, yans[0].second);
    return 0;
}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
zoltan.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 140 / 140