Submission #1061273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061273		MilosMilutinovic	Tricks of the Trade (CEOI23_trade)	C++14	100 / 100	2650 ms	192900 KiB

trade

#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;
  };
  vector<pair<int, int>> segs;
  vector<int> idx(n);
  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 = max(0, optl); i <= min(mid, optr); i++) {
      long long v = Calc(i, mid);
      if (v >= best && v != inf) {
        best = v;
        opt = i;
      }
    }
    res = max(res, best);
    idx[mid] = opt;
    Solve(l, mid - 1, optl, opt);
    Solve(mid + 1, r, opt, optr);
  };
  Solve(0, n - 1, 0, n - 1);
  cout << res << '\n';
  vector<int> ids;
  for (int i = 0; i < n; i++) {
    if (Calc(idx[i], i) == res) {
      ids.push_back(i);
    }
  }
  int ptr = 0;
  for (int b = 0; b < (int) ids.size(); b++) {
    int i = ids[b];
    while (ptr <= idx[i]) {
      segs.emplace_back(ptr, i);
      if (b > 0) {
        segs.emplace_back(ptr, ids[b - 1]);
      }
      if (b + 1 < (int) ids.size()) {
        segs.emplace_back(ptr, ids[b + 1]);
      }
      ptr += 1;
    }
    ptr = max(ptr - 1, 0);
  }
  vector<int> seq(n, 0);
  vector<vector<int>> qs(n + 1);
  for (auto& p : segs) {
    int l = p.first;
    int r = p.second;
    if (l > r || Calc(l, r) != res) {
      continue;
    }
    int el = Walk(root[r], l == 0 ? 0 : root[l - 1], 0, MAX, k);
    qs[l].push_back(el);
    qs[r + 1].push_back(~el);
  }
  multiset<int> st;
  for (int i = 0; i < n; i++) {
    for (int j : qs[i]) {
      if (j >= 0) {
        st.insert(j);
      } else {
        st.erase(st.find(~j));
      }
    }
    if (!st.empty() && s[i] >= *st.begin()) {
      seq[i] = 1;
    }
  }
  for (int i = 0; i < n; i++) {
    cout << seq[i];
  }
  cout << '\n';
  return 0;
}

Compilation message (stderr)

trade.cpp: In function 'int main()':
trade.cpp:94:7: warning: unused variable 'from' [-Wunused-variable]
   94 |   int from = -1, to = -1;
      |       ^~~~
trade.cpp:94:18: warning: unused variable 'to' [-Wunused-variable]
   94 |   int from = -1, to = -1;
      |                  ^~

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45