Submission #1060792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060792		MilosMilutinovic	Tricks of the Trade (CEOI23_trade)	C++14	20 / 100	8061 ms	174372 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;
  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) {
          segs.clear();
          res = best;
          segs.emplace_back(opt, mid);
        } else if (best == res) {
          segs.emplace_back(opt, mid);
        }
      } else if (v == best) {
        if (best > res) {
          segs.clear();
          res = best;
          segs.emplace_back(i, mid);
        } else if (best == res) {
          segs.emplace_back(i, 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> seq(n, 0);
  vector<vector<int>> qs(n + 1);
  for (auto& p : segs) {
    int l = p.first;
    int r = p.second;
    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);
    for (int i = l; i <= r; i++) {
      if (s[i] >= el) {
        seq[i] = 1;
      }
    }
  }
  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: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45