Submission #253649

#	Time	Username	Problem	Language	Result	Execution time	Memory
253649		NONAME	Zoltan (COCI16_zoltan)	C++14	21 / 140	694 ms	3832 KiB

zoltan

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;

const int N = int(1e5) + 500;
const int base = int(1e9) + 7;

int n, mn, mx, ans;
int fen[N], a[N], f[N], c[N];

int add(int x, int y) {
    x += y;
    if (x > base)
        x -= base;
    return x;
}

void upd(int x, int vl) { while (x < n) fen[x] = max(fen[x], vl), x = (x | (x + 1)); }
int f_max(int x) { int k = 0; while (x >= 0) k = max(k, fen[x]), x = (x & (x + 1)) - 1; return k; }

bool cmp(int x, int y) { return a[x] < a[y]; }

int main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i], c[i] = i;
    sort(c, c + n, cmp);
    int cur = 0;
    for (int i = 1; i < n; ++i)
        if (a[c[i]] == a[c[i - 1]]) a[c[i - 1]] = cur;
            else a[c[i - 1]] = cur++;
    a[c[n - 1]] = cur;

    mn = mx = a[0];
    ans = 1;
    for (int i = 1; i < n; ++i) {
        if (a[i] < mn) ++ans, mn = a[i];
        if (a[i] > mx) ++ans, mx = a[i];
    }

    cout << ans << " ";
    int res = 0;
    if (n <= 20) {
        for (int msk = 0; msk < (1 << (n - 1)); ++msk) {
            vector <int> l, r;
            for (int i = 1; i < n; ++i)
                if (msk & (1 << (i - 1))) r.push_back(a[i]);
                    else l.push_back(a[i]);

            reverse(l.begin(), l.end());
            vector <int> v;

            for (int i : l)
                v.push_back(i);
            v.push_back(a[0]);
            for (int i : r)
                v.push_back(i);

            for (int i = 0; i < n; ++i)
                fen[i] = 0;
            for (int i = 0; i < n; ++i) {
                f[i] = f_max(v[i] - 1) + 1;
                upd(i, f[i]);
            }

            for (int i = 0; i < n; ++i)
                if (fen[i] == ans)
                    res = add(res, 1);
        }
    }

    cout << res << "\n";
}

• Subtask 1: 21 / 140