제출 #1060772

#제출 시각아이디문제언어결과실행 시간메모리
1060772MilosMilutinovicTricks of the Trade (CEOI23_trade)C++14
50 / 100
2021 ms163368 KiB
#include <bits/stdc++.h> using namespace std; const int N = 250000; const int MAX = (int) 1.00001e9; int root[N * 60], ch[N * 60][2], cnt[N * 60], tsz; long long sum[N * 60]; void Modify(int& x, int y, int l, int r, int i) { x = ++tsz; ch[x][0] = ch[y][0]; ch[x][1] = ch[y][1]; sum[x] = sum[y] + i; cnt[x] = cnt[y] + 1; if (l == r) { return; } int mid = (l + r) >> 1; if (i <= mid) { Modify(ch[x][0], ch[y][0], l, mid, i); } else { Modify(ch[x][1], ch[y][1], mid + 1, r, i); } } int Walk(int x, int y, int l, int r, int k) { if (l == r) { return l; } int mid = (l + r) >> 1; if (cnt[ch[x][1]] - cnt[ch[y][1]] >= k) { return Walk(ch[x][1], ch[y][1], mid + 1, r, k); } else { return Walk(ch[x][0], ch[y][0], l, mid, k - (cnt[ch[x][1]] - cnt[ch[y][1]])); } } int QueryCnt(int x, int y, int l, int r, int ll, int rr) { if (ll <= l && r <= rr) { return cnt[x] - cnt[y]; } int mid = (l + r) >> 1; if (rr <= mid) { return QueryCnt(ch[x][0], ch[y][0], l, mid, ll, rr); } else if (ll > mid) { return QueryCnt(ch[x][1], ch[y][1], mid + 1, r, ll, rr); } else { return QueryCnt(ch[x][0], ch[y][0], l, mid, ll, rr) + QueryCnt(ch[x][1], ch[y][1], mid + 1, r, ll, rr); } } long long QuerySum(int x, int y, int l, int r, int ll, int rr) { if (ll <= l && r <= rr) { return sum[x] - sum[y]; } int mid = (l + r) >> 1; if (rr <= mid) { return QuerySum(ch[x][0], ch[y][0], l, mid, ll, rr); } else if (ll > mid) { return QuerySum(ch[x][1], ch[y][1], mid + 1, r, ll, rr); } else { return QuerySum(ch[x][0], ch[y][0], l, mid, ll, rr) + QuerySum(ch[x][1], ch[y][1], mid + 1, r, ll, rr); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<int> c(n); for (int i = 0; i < n; i++) { cin >> c[i]; } vector<int> s(n); for (int i = 0; i < n; i++) { cin >> s[i]; } vector<long long> pref(n); for (int i = 0; i < n; i++) { pref[i] = (i == 0 ? 0LL : pref[i - 1]) + c[i]; } for (int i = 0; i < n; i++) { if (i > 0) { root[i] = root[i - 1]; } Modify(root[i], root[i], 0, MAX, s[i]); } const long long inf = (long long) -1e18; long long res = inf; int from = -1, to = -1; auto Calc = [&](int l, int r) { if (r - l + 1 < k) { return inf; } long long ret = -(pref[r] - (l == 0 ? 0LL : pref[l - 1])); int el = Walk(root[r], l == 0 ? 0 : root[l - 1], 0, MAX, k); int c = QueryCnt(root[r], l == 0 ? 0 : root[l - 1], 0, MAX, el + 1, MAX); ret += QuerySum(root[r], l == 0 ? 0 : root[l - 1], 0, MAX, el + 1, MAX); ret += el * 1LL * (k - c); return ret; }; function<void(int, int, int, int)> Solve = [&](int l, int r, int optl, int optr) { if (l > r) { return; } int mid = (l + r) >> 1; int opt = min(optl, mid); long long best = Calc(opt, mid); for (int i = optl; i <= min(mid, optr); i++) { long long v = Calc(i, mid); if (v > best) { best = v; opt = i; } } if (best > res) { res = best; from = opt; to = mid; } Solve(l, mid - 1, optl, opt); Solve(mid + 1, r, opt, optr); }; Solve(0, n - 1, 0, n - 1); cout << res << '\n'; vector<int> order; for (int i = from; i <= to; i++) { order.push_back(i); } sort(order.begin(), order.end(), [&](int i, int j) { return s[i] > s[j]; }); vector<int> seq(n, 0); for (int i = 0; i < min(k, (int) order.size()); i++) { seq[order[i]] = 1; } for (int i = 0; i < n; i++) { cout << seq[i]; } cout << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...