Submission #1284811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284811		adscoding	Zoltan (COCI16_zoltan)	C++20	140 / 140	127 ms	8436 KiB

zoltan

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxn = 4e5 + 3, MOD = 1e9 + 7;
int n, a[maxn];
vector<int> ids;

void add(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}

pii combine(pii x, pii y)
{
    pii res;
    if (x.first > y.first) swap(x, y);
    if (x.first < y.first) res.first = y.first, res.second = y.second;
    else if (x.first == y.first) res.first = y.first, res.second = (x.second + y.second) % MOD;
    return res;
}

struct FenTreeDown
{
    vector<pii> fw; int n;

    void init(int _n)
    {
        n = _n + 2;
        fw.clear();
        fw.assign(n + 5, make_pair(0, 0));
    }

    void upd(int pos, pii val)
    {
        ++pos;
        for (; pos <= n; pos += pos & -pos) fw[pos] = combine(fw[pos], val);
    }

    pii get(int pos)
    {
        ++pos;
        pii res = {0, 0};
        for (; pos; pos &= pos - 1) res = combine(res, fw[pos]);
        return res;
    }
};

pii dp[maxn];

int binpow(int a, int b)
{
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % MOD)
        if (b & 1) res = 1ll * res * a % MOD;
    return res;
}

void solve()
{
    cin >> n;
    FOR(i, 1, n) cin >> a[i], ids.push_back(a[i]), a[i + n] = a[i];
    FOR(i, 1, n / 2) swap(a[i], a[n - i + 1]);

    vector<int> vec;

    sort(all(ids)); ids.erase(unique(all(ids)), ids.end());
    FOR(i, 1, n << 1)
    {
        a[i] = lower_bound(all(ids), a[i]) - ids.begin() + 1;
        if (vec.empty() || vec.back() < a[i]) vec.push_back(a[i]);
        else vec[lower_bound(all(vec), a[i]) - vec.begin()] = a[i];
    }
    int lis = (int)vec.size();
    int res = 0;

    FenTreeDown fwleft;
    fwleft.init(n);

    fwleft.upd(0, {0, 1});
    FOR(i, 1, n)
    {
        pii cur = fwleft.get(a[i] - 1);
        dp[i] = make_pair(cur.first + 1, cur.second);
        fwleft.upd(a[i], dp[i]);

        if (dp[i].first == lis) add(res, dp[i].second);
    }

    fwleft.init(n);

    FOR(i, n + 1, n << 1)
    {
        pii cur = fwleft.get(a[i] - 1);
        dp[i] = make_pair(cur.first + 1, cur.second);

        if (dp[i].first == lis) add(res, dp[i].second);

        fwleft.upd(a[i], dp[i]);
        fwleft.upd(a[i], dp[n *  2 - i + 1]);
    }

    res = 1ll * res * binpow(2, n - lis) % MOD;
    cout << lis << ' ' << res;
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #define TASK "TEST"
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    solve();
    return 0;
}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140