제출 #1310186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310186		nikile	Zoltan (COCI16_zoltan)	C++20	35 / 140	1097 ms	19328 KiB

zoltan

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#ifndef nikile
    #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    #pragma GCC optimize("O3,unroll-loops")
#endif

const int mod = 1e9 + 7;

int add(int a, int b) {
    if (a + b >= mod) {
        return a + b - mod;
    } else {
        return a + b;
    }
}

int sub(int a, int b) {
    if (a < b) {
        return a - b + mod;
    } else {
        return a - b;
    }
}

int mul(int a, int b) {
    return 1ll * a * b % mod;
}

struct node {
    int val = 0, cnt = 1;
    node(int a, int b) {
        val = a;
        cnt = b;
    }
    node() {
        val = 0;
        cnt = 1;
    }
};

struct segtree {
    vector<node> t;
    segtree(int n) {
        t.resize(4 * n);
    }
    node merge(node &a, node &b) {
        node m = a;
        if (a.val == 0) {
            return b;
        }
        if (b.val == 0) {
            return a;
        } 
        if (a.val == b.val) {
            m.cnt = add(a.cnt, b.cnt);
        } else if (a.val < b.val) {
            m = b;
        }
        return m;
    }
    void upd(int lx, int rx, int x, int i, node v) {
        if (lx + 1 == rx) {
            t[x] = v;
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m) {
            upd(lx, m, 2 * x + 1, i, v);
        } else {
            upd(m, rx, 2 * x + 2, i, v);
        }
        t[x] = merge(t[2 * x + 1], t[2 * x + 2]);
    }
    node get(int lx, int rx, int x, int l, int r) {
        if (lx >= r || l >= rx) {
            return {0, 1};
        }
        if (l <= lx && rx <= r) {
            return t[x];
        }
        int m = (lx + rx) / 2;
        node A = get(lx, m, 2 * x + 1, l, r);
        node B = get(m, rx, 2 * x + 2, l, r);
        return merge(A, B);
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), pw(n + 1, 1);
    vector<pair<int, int>> s(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s[i].first = a[i];
        s[i].second = i;
        pw[i + 1] = mul(pw[i], 2);
    }
    sort(all(s));
    segtree t1(n), t2(n);
    vector<int> dp1(n), cnt1(n), dp2(n), cnt2(n);
    for (int i = n - 1; i >= 0; i--) {
        int it = lower_bound(all(s), make_pair(a[i], i)) - s.begin();
        int pos = upper_bound(all(s), make_pair(a[i], n)) - s.begin();
        node now = t1.get(0, n, 0, pos, n);
        dp1[i] = now.val + 1;
        cnt1[i] = now.cnt;
        t1.upd(0, n, 0, it, node(dp1[i], cnt1[i]));
        pos = lower_bound(all(s), make_pair(a[i], 0)) - s.begin() - 1;
        now = t2.get(0, n, 0, 0, it);
        dp2[i] = now.val + 1;
        cnt2[i] = now.cnt;
        t2.upd(0, n, 0, it, node(dp2[i], cnt2[i]));
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int mx = 0;
        for (int j = 0; j < n; j++) {
            if (a[i] > a[j]) {
                mx = max(mx, dp2[j]);
            }
        }
        ans = max(ans, mx + dp1[i]);
    }
    int cnt = 0, x = *max_element(all(dp1));
    for (int i = 0; i < n; i++) {
        if (dp1[i] != x) continue;
        for (int j = 0; j < n; j++) {
            if (a[i] > a[j] && dp1[i] + dp2[j] == ans) {
                cnt = add(cnt, mul(pw[n - ans], mul(cnt1[i], cnt2[j])));
            }
        }
        if (dp1[i] == ans) {
            cnt = add(cnt, mul(pw[n - ans], cnt1[i]));
        }
    }
    cout << ans << " " << cnt << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef nikile
        freopen("input.txt", "r", stdin);
    #endif
    solve();
    return 0;
}

• Subtask 1: 35 / 140