QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#130255#5035. foo~pandapythoner#Compile Error//C++206.8kb2023-07-23 18:57:192024-07-04 00:55:16

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 00:55:16]
  • 评测
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-23 18:57:19]
  • 提交

answer

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#else
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#endif

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(234);

struct SGT_add_max {
    int n;
    vector<ll> t;
    vector<ll> d;

    void upd(int v) {
        t[v] = max(t[v + v], t[v + v + 1]) + d[v];
    }

    void apply(int v, ll x) {
        t[v] += x;
        d[v] += x;
    }

    void push(int v) {
        return;
        apply(v + v, d[v]);
        apply(v + v + 1, d[v]);
        d[v] = 0;
    }

    void build(int _n) {
        n = _n;
        t.assign(n * 4, 0);
        d.assign(n * 4, 0);
    }

    void build(int v, int tl, int tr, const vector<int> &a) {
        if (tl == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(v + v, tl, tm, a);
        build(v + v + 1, tm + 1, tr, a);
        upd(v);
    }

    void build(const vector<int> &a) {
        n = a.size();
        t.assign(n * 4, 0);
        d.assign(n * 4, 0);
        build(1, 0, n - 1, a);
    }

    void add(int v, int tl, int tr, int l, int r, ll x) {
        if (l <= tl && tr <= r) {
            apply(v, x);
            return;
        }
        int tm = (tl + tr) / 2;
        push(v);
        if (r <= tm) {
            add(v + v, tl, tm, l, r, x);
        } else if (tm + 1 <= l) {
            add(v + v + 1, tm + 1, tr, l, r, x);
        } else {
            add(v + v, tl, tm, l, r, x);
            add(v + v + 1, tm + 1, tr, l, r, x);
        }
        upd(v);
    }

    void add(int l, int r, ll x) {
        if (l > r) {
            return;
        }
        add(1, 0, n - 1, l, r, x);
    }

    ll get(int v, int tl, int tr, ll r) {
        if (tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        push(v);
        if (r <= tm) {
            return get(v + v, tl, tm, r) + d[v];
        } else {
            return max(get(v + v, tl, tm, r), get(v + v + 1, tm + 1, tr, r)) + d[v];
        }
    }

    ll get(int l, int r) {
        if (l > r) {
            return 0;
        }
        return get(1, 0, n - 1, r);
    }
};

int n, k;
vector<int> a;

ll solve_slow(vector<int> b) {
    if (k == 1) {
        int rs = 0;
        int mx = -1;
        int cnt = 0;
        vector<int> stck;
        for (int i = 0; i < n; i += 1) {
            if (b[i] >= mx) {
                cnt += 1;
                mx = b[i];
            }
            rs = max(rs, cnt);
            while (!stck.empty() && stck.back() < b[i]) {
                stck.pop_back();
            }
            stck.push_back(b[i]);
            rs = max(rs, (int)stck.size());
        }
        return rs;
    }
    vector<vector<int>> d(n + 1, vector<int>(n + 1, 0));
    for (int l = 0; l <= n; l += 1) {
        int mx = -1;
        int cnt = 0;
        for (int r = l + 1; r <= n; r += 1) {
            if (b[r - 1] >= mx) {
                mx = b[r - 1];
                cnt += 1;
            }
            d[l][r] = max(d[l][r], cnt);
        }
    }
    for (int r = n; r >= 0; r -= 1) {
        int mx = -1;
        int cnt = 0;
        for (int l = r - 1; l >= 0; l -= 1) {
            if (b[l] >= mx) {
                mx = b[l];
                cnt += 1;
            }
            d[l][r] = max(d[l][r], cnt);
        }
    }
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, -n));
    dp[0][0] = 0;
    int rs = 0;
    for (int i = 1; i <= n; i += 1) {
        for (int j = 0; j < i; j += 1) {
            for (int c = 0; c < k; c += 1) {
                dp[i][c + 1] = max(dp[i][c + 1], dp[j][c] + d[j][i]);
            }
        }
        rs = max(rs, dp[i][k]);
    }
    return rs;
}

ll solve_slow() {
    if (n == 1) {
        return 1;
    }
    auto b = a;
    int mx_i = 0;
    for (int i = 1; i < n; i += 1) {
        if (b[i] > b[mx_i]) {
            mx_i = i;
        }
    }
    rotate(b.begin(), b.begin() + mx_i, b.end());
    ll rs = solve_slow(b);
    rotate(b.begin(), b.begin() + 1, b.end());
    reverse(all(b));
    rs = max(rs, solve_slow(b));
    /*
    for(int itr = 0; itr < n; itr += 1){
        rotate(b.begin(), b.begin() + 1, b.end());
        rs = max(rs, solve_slow(b));
    }
    */
    return rs;
}

ll solve(vector<int> b) {
    vector<int> dp(n + 1, -n * 10);
    dp[0] = 0;
    int rs = 0;
    for (int itr = 0; itr < k; itr += 1) {
        SGT_add_max sgt2;
        sgt2.build(dp);
        vector<pair<int, int>> stck;
        vector<int> stck1;
        stck1.push_back(-n);
        stck.push_back(make_pair(n + 10, 0));
        vector<int> ndp(n + 1, 0);
        int pmx = 0;
        for (int i = 1; i <= n; i += 1) {
            int x = b[i - 1];
            while (!stck.empty() && stck.back().first < x) {
                // int pos = stck.back().second;
                stck1.pop_back();
                stck.pop_back();
            }
            int prvs_bgr = stck.back().second;
            sgt2.add(prvs_bgr, i - 1, 1);
            stck.push_back(make_pair(x, i));
            stck1.push_back(max(stck1.back() + 1, pmx + 1));
            ndp[i] = max(stck1.back(), (int)sgt2.get(0, i - 1));
            rs = max(rs, ndp[i]);
            pmx = max(pmx, dp[i]);
        }
        dp.swap(ndp);
    }
    return rs;
}

ll solve() {
    if (n == 1) {
        return 1;
    }
    auto b = a;
    int mx_i = 0;
    for (int i = 1; i < n; i += 1) {
        if (b[i] > b[mx_i]) {
            mx_i = i;
        }
    }
    rotate(b.begin(), b.begin() + mx_i, b.end());
    ll rs = solve(b);
    rotate(b.begin(), b.begin() + 1, b.end());
    reverse(all(b));
    rs = max(rs, solve(b));
    return rs;
}

void gen_test() {
    n = rnd() % 7 + 1;
    k = rnd() % n + 1;
    a.resize(n);
    for (int i = 0; i < n; i += 1) {
        a[i] = i;
    }
    shuffle(all(a), rnd);
}

void print_test() {
    cout << n << " " << k << "\n";
    for (auto t : a) {
        cout << t + 1 << " ";
    }
    cout << "\n";
}

void stress() {
    int c = 0;
    while (1) {
        cout << ++c << "\n";
        gen_test();
        ll right_rs = solve_slow();
        ll my_rs = solve();
        if (right_rs != my_rs) {
            print_test();
            break;
        }
    }
}

int32_t main() {
    // stress();
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; i += 1) {
        cin >> a[i];
        --a[i];
    }
    ll rs = solve();
    cout << rs << "\n";
    return 0;
}

/*
7 2
6 5 1 7 3 2 4


*/

详细

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:8:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~