oj.uz

답안 #1060805

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1060805 2024-08-15T23:04:20 Z MilosMilutinovic Tricks of the Trade (CEOI23_trade) C++14
5 / 100
 2504 ms 179248 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 = 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) {
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1370 ms 179248 KB Output is correct
3 Correct 1171 ms 165036 KB Output is correct
4 Correct 2122 ms 166600 KB Output is correct
5 Partially correct 2504 ms 172740 KB Partially correct
6 Partially correct 2070 ms 174432 KB Partially correct
7 Correct 2341 ms 177012 KB Output is correct
8 Correct 1129 ms 168904 KB Output is correct
9 Correct 1237 ms 165836 KB Output is correct
10 Correct 1337 ms 176188 KB Output is correct

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1370 ms 179248 KB Output is correct
3 Correct 1171 ms 165036 KB Output is correct
4 Correct 2122 ms 166600 KB Output is correct
5 Partially correct 2504 ms 172740 KB Partially correct
6 Partially correct 2070 ms 174432 KB Partially correct
7 Correct 2341 ms 177012 KB Output is correct
8 Correct 1129 ms 168904 KB Output is correct
9 Correct 1237 ms 165836 KB Output is correct
10 Correct 1337 ms 176188 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1394 ms 179248 KB Output is correct
13 Correct 1171 ms 165036 KB Output is correct
14 Correct 2122 ms 169484 KB Output is correct
15 Partially correct 2344 ms 176908 KB Partially correct
16 Partially correct 2017 ms 174380 KB Partially correct
17 Correct 2289 ms 178168 KB Output is correct
18 Correct 1169 ms 167412 KB Output is correct
19 Correct 1262 ms 167032 KB Output is correct
20 Correct 1446 ms 177616 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 604 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 -