oj.uz

Submission #1060781

# Submission time Handle Problem Language Result Execution time Memory
1060781 2024-08-15T22:35:57 Z MilosMilutinovic Tricks of the Trade (CEOI23_trade) C++14
5 / 100
 1965 ms 161984 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;
  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);
    }
    Solve(l, mid - 1, optl, opt);
    Solve(mid + 1, r, opt, optr);
  };
  Solve(0, n - 1, 0, n - 1);
  cout << res << '\n';
  if (n > 6000) {
    return 0;
  }
  vector<int> seq(n, 0);
  for (auto& p : segs) {
    int l = p.first;
    int r = p.second;
    vector<int> v;
    for (int i = l; i <= r; i++) {
      v.push_back(s[i]);
    }
    sort(v.rbegin(), v.rend());
    for (int i = l; i <= r; i++) {
      if (s[i] >= v[k - 1]) {
        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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 600 KB Output is correct
2 Partially correct 1008 ms 161740 KB Partially correct
3 Partially correct 1043 ms 158116 KB Partially correct
4 Partially correct 1736 ms 159272 KB Partially correct
5 Partially correct 1869 ms 159960 KB Partially correct
6 Partially correct 1633 ms 161328 KB Partially correct
7 Partially correct 1965 ms 160592 KB Partially correct
8 Partially correct 966 ms 160832 KB Partially correct
9 Partially correct 1051 ms 159340 KB Partially correct
10 Partially correct 1037 ms 160560 KB Partially correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Partially correct 1008 ms 161740 KB Partially correct
3 Partially correct 1043 ms 158116 KB Partially correct
4 Partially correct 1736 ms 159272 KB Partially correct
5 Partially correct 1869 ms 159960 KB Partially correct
6 Partially correct 1633 ms 161328 KB Partially correct
7 Partially correct 1965 ms 160592 KB Partially correct
8 Partially correct 966 ms 160832 KB Partially correct
9 Partially correct 1051 ms 159340 KB Partially correct
10 Partially correct 1037 ms 160560 KB Partially correct
11 Correct 0 ms 344 KB Output is correct
12 Partially correct 1002 ms 161984 KB Partially correct
13 Partially correct 986 ms 159300 KB Partially correct
14 Partially correct 1725 ms 159276 KB Partially correct
15 Partially correct 1854 ms 161496 KB Partially correct
16 Partially correct 1661 ms 161240 KB Partially correct
17 Partially correct 1944 ms 159056 KB Partially correct
18 Partially correct 941 ms 160592 KB Partially correct
19 Partially correct 1029 ms 160824 KB Partially correct
20 Partially correct 999 ms 161812 KB Partially correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Incorrect 0 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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 -