oj.uz

Submission #1060808

# Submission time Handle Problem Language Result Execution time Memory
1060808 2024-08-15T23:09:32 Z MilosMilutinovic Tricks of the Trade (CEOI23_trade) C++14
5 / 100
 2207 ms 181280 KB 
#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 = 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;
    }
  }
  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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 472 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Incorrect 0 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 472 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Incorrect 0 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1287 ms 181280 KB Output is correct
3 Correct 1070 ms 168408 KB Output is correct
4 Correct 1879 ms 169912 KB Output is correct
5 Partially correct 2186 ms 175904 KB Partially correct
6 Partially correct 1972 ms 176292 KB Partially correct
7 Correct 2089 ms 179916 KB Output is correct
8 Correct 1054 ms 169428 KB Output is correct
9 Correct 1138 ms 168396 KB Output is correct
10 Correct 1317 ms 179036 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1287 ms 181280 KB Output is correct
3 Correct 1070 ms 168408 KB Output is correct
4 Correct 1879 ms 169912 KB Output is correct
5 Partially correct 2186 ms 175904 KB Partially correct
6 Partially correct 1972 ms 176292 KB Partially correct
7 Correct 2089 ms 179916 KB Output is correct
8 Correct 1054 ms 169428 KB Output is correct
9 Correct 1138 ms 168396 KB Output is correct
10 Correct 1317 ms 179036 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1295 ms 181272 KB Output is correct
13 Correct 1099 ms 168568 KB Output is correct
14 Correct 1854 ms 169912 KB Output is correct
15 Partially correct 2207 ms 175904 KB Partially correct
16 Partially correct 1936 ms 176176 KB Partially correct
17 Correct 2136 ms 179908 KB Output is correct
18 Correct 1078 ms 169256 KB Output is correct
19 Correct 1127 ms 168360 KB Output is correct
20 Correct 1382 ms 179152 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Incorrect 1 ms 604 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 472 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Incorrect 0 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -