QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#130255 | #5035. foo~ | pandapythoner# | Compile Error | / | / | C++20 | 6.8kb | 2023-07-23 18:57:19 | 2024-07-04 00:55:16 |
Judging History
你现在查看的是最新测评结果
- [2024-07-04 00:55:16]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [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 | ^~~~~~~~~~~~