oj.uz

Submission #253649

# Submission time Handle Problem Language Result Execution time Memory
253649 2020-07-28T13:39:03 Z NONAME Zoltan (COCI16_zoltan) C++14
21 / 140
 694 ms 3832 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 676 ms 504 KB Output isn't correct
2 Incorrect 682 ms 384 KB Output isn't correct
3 Incorrect 694 ms 384 KB Output isn't correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 673 ms 504 KB Output is correct
6 Correct 620 ms 384 KB Output is correct
7 Incorrect 1 ms 384 KB Output isn't correct
8 Incorrect 1 ms 384 KB Output isn't correct
9 Incorrect 1 ms 384 KB Output isn't correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Incorrect 36 ms 2808 KB Output isn't correct
12 Incorrect 31 ms 2432 KB Output isn't correct
13 Incorrect 29 ms 2304 KB Output isn't correct
14 Incorrect 50 ms 2808 KB Output isn't correct
15 Incorrect 50 ms 3320 KB Output isn't correct
16 Incorrect 57 ms 3832 KB Output isn't correct
17 Incorrect 59 ms 3192 KB Output isn't correct
18 Incorrect 46 ms 3200 KB Output isn't correct
19 Incorrect 43 ms 3200 KB Output isn't correct
20 Incorrect 46 ms 3192 KB Output isn't correct