oj.uz

Submission #1060786

# Submission time Handle Problem Language Result Execution time Memory
1060786 2024-08-15T22:40:28 Z MilosMilutinovic Tricks of the Trade (CEOI23_trade) C++14
55 / 100
 2033 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 > 500) {
    return 0;
  }
  for (auto& p : segs) {
    assert(Calc(p.first, p.second) == res);
  }
  vector<int> seq(n, 0);
  for (int l = 0; l < n; l++) {
    for (int r = l + k - 1; r < n; r++) {
      if (Calc(l, r) != res) {
        continue;
      }
      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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
10.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 2 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 6 ms 432 KB Output is correct
7 Correct 4 ms 612 KB Output is correct
8 Correct 6 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 7 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct

Subtask #2
5.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 2 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 6 ms 432 KB Output is correct
7 Correct 4 ms 612 KB Output is correct
8 Correct 6 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 7 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 6 ms 604 KB Output is correct
18 Correct 5 ms 604 KB Output is correct
19 Correct 6 ms 604 KB Output is correct
20 Correct 4 ms 604 KB Output is correct
21 Correct 5 ms 604 KB Output is correct
22 Correct 5 ms 604 KB Output is correct
23 Partially correct 3 ms 6236 KB Partially correct
24 Partially correct 30 ms 6136 KB Partially correct
25 Partially correct 26 ms 5980 KB Partially correct
26 Partially correct 30 ms 5980 KB Partially correct
27 Partially correct 18 ms 6124 KB Partially correct
28 Partially correct 20 ms 5980 KB Partially correct
29 Partially correct 10 ms 5976 KB Partially correct

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 1092 ms 159452 KB Partially correct
3 Partially correct 991 ms 160828 KB Partially correct
4 Partially correct 1702 ms 160596 KB Partially correct
5 Partially correct 1860 ms 159704 KB Partially correct
6 Partially correct 1617 ms 161236 KB Partially correct
7 Partially correct 1953 ms 160592 KB Partially correct
8 Partially correct 954 ms 160596 KB Partially correct
9 Partially correct 1020 ms 159308 KB Partially correct
10 Partially correct 1010 ms 161984 KB Partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 1092 ms 159452 KB Partially correct
3 Partially correct 991 ms 160828 KB Partially correct
4 Partially correct 1702 ms 160596 KB Partially correct
5 Partially correct 1860 ms 159704 KB Partially correct
6 Partially correct 1617 ms 161236 KB Partially correct
7 Partially correct 1953 ms 160592 KB Partially correct
8 Partially correct 954 ms 160596 KB Partially correct
9 Partially correct 1020 ms 159308 KB Partially correct
10 Partially correct 1010 ms 161984 KB Partially correct
11 Correct 1 ms 348 KB Output is correct
12 Partially correct 1062 ms 160548 KB Partially correct
13 Partially correct 998 ms 160640 KB Partially correct
14 Partially correct 1720 ms 160672 KB Partially correct
15 Partially correct 1836 ms 159744 KB Partially correct
16 Partially correct 1604 ms 161660 KB Partially correct
17 Partially correct 1943 ms 159152 KB Partially correct
18 Partially correct 952 ms 160592 KB Partially correct
19 Partially correct 1052 ms 159568 KB Partially correct
20 Partially correct 1032 ms 160552 KB Partially correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 2 ms 600 KB Output is correct
24 Correct 1 ms 600 KB Output is correct
25 Correct 6 ms 604 KB Output is correct
26 Correct 5 ms 600 KB Output is correct
27 Correct 6 ms 604 KB Output is correct
28 Correct 4 ms 608 KB Output is correct
29 Correct 5 ms 604 KB Output is correct
30 Correct 5 ms 604 KB Output is correct
31 Partially correct 999 ms 160828 KB Partially correct
32 Partially correct 2033 ms 159700 KB Partially correct
33 Partially correct 1878 ms 159916 KB Partially correct
34 Partially correct 1626 ms 161240 KB Partially correct
35 Partially correct 1447 ms 159572 KB Partially correct
36 Partially correct 1624 ms 160832 KB Partially correct
37 Partially correct 1348 ms 161744 KB Partially correct

Subtask #5
25.0 / 45.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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 6 ms 432 KB Output is correct
9 Correct 4 ms 612 KB Output is correct
10 Correct 6 ms 604 KB Output is correct
11 Correct 4 ms 604 KB Output is correct
12 Correct 7 ms 604 KB Output is correct
13 Correct 5 ms 604 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 6 ms 604 KB Output is correct
20 Correct 5 ms 604 KB Output is correct
21 Correct 6 ms 604 KB Output is correct
22 Correct 4 ms 604 KB Output is correct
23 Correct 5 ms 604 KB Output is correct
24 Correct 5 ms 604 KB Output is correct
25 Partially correct 3 ms 6236 KB Partially correct
26 Partially correct 30 ms 6136 KB Partially correct
27 Partially correct 26 ms 5980 KB Partially correct
28 Partially correct 30 ms 5980 KB Partially correct
29 Partially correct 18 ms 6124 KB Partially correct
30 Partially correct 20 ms 5980 KB Partially correct
31 Partially correct 10 ms 5976 KB Partially correct
32 Correct 0 ms 344 KB Output is correct
33 Partially correct 1092 ms 159452 KB Partially correct
34 Partially correct 991 ms 160828 KB Partially correct
35 Partially correct 1702 ms 160596 KB Partially correct
36 Partially correct 1860 ms 159704 KB Partially correct
37 Partially correct 1617 ms 161236 KB Partially correct
38 Partially correct 1953 ms 160592 KB Partially correct
39 Partially correct 954 ms 160596 KB Partially correct
40 Partially correct 1020 ms 159308 KB Partially correct
41 Partially correct 1010 ms 161984 KB Partially correct
42 Correct 1 ms 348 KB Output is correct
43 Partially correct 1062 ms 160548 KB Partially correct
44 Partially correct 998 ms 160640 KB Partially correct
45 Partially correct 1720 ms 160672 KB Partially correct
46 Partially correct 1836 ms 159744 KB Partially correct
47 Partially correct 1604 ms 161660 KB Partially correct
48 Partially correct 1943 ms 159152 KB Partially correct
49 Partially correct 952 ms 160592 KB Partially correct
50 Partially correct 1052 ms 159568 KB Partially correct
51 Partially correct 1032 ms 160552 KB Partially correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 2 ms 600 KB Output is correct
55 Correct 1 ms 600 KB Output is correct
56 Correct 6 ms 604 KB Output is correct
57 Correct 5 ms 600 KB Output is correct
58 Correct 6 ms 604 KB Output is correct
59 Correct 4 ms 608 KB Output is correct
60 Correct 5 ms 604 KB Output is correct
61 Correct 5 ms 604 KB Output is correct
62 Partially correct 999 ms 160828 KB Partially correct
63 Partially correct 2033 ms 159700 KB Partially correct
64 Partially correct 1878 ms 159916 KB Partially correct
65 Partially correct 1626 ms 161240 KB Partially correct
66 Partially correct 1447 ms 159572 KB Partially correct
67 Partially correct 1624 ms 160832 KB Partially correct
68 Partially correct 1348 ms 161744 KB Partially correct
69 Correct 0 ms 348 KB Output is correct
70 Partially correct 1044 ms 160732 KB Partially correct
71 Partially correct 1006 ms 160596 KB Partially correct
72 Partially correct 1708 ms 160828 KB Partially correct
73 Partially correct 1866 ms 159748 KB Partially correct
74 Partially correct 1616 ms 159700 KB Partially correct
75 Partially correct 1942 ms 160596 KB Partially correct
76 Partially correct 960 ms 160832 KB Partially correct
77 Partially correct 1020 ms 159340 KB Partially correct
78 Partially correct 1012 ms 161744 KB Partially correct
79 Correct 1 ms 344 KB Output is correct
80 Correct 0 ms 348 KB Output is correct
81 Correct 2 ms 604 KB Output is correct
82 Correct 0 ms 604 KB Output is correct
83 Correct 8 ms 604 KB Output is correct
84 Correct 4 ms 612 KB Output is correct
85 Correct 6 ms 604 KB Output is correct
86 Correct 5 ms 608 KB Output is correct
87 Correct 5 ms 608 KB Output is correct
88 Correct 5 ms 612 KB Output is correct
89 Partially correct 1034 ms 160828 KB Partially correct
90 Partially correct 1939 ms 161460 KB Partially correct
91 Partially correct 1847 ms 161240 KB Partially correct
92 Partially correct 1611 ms 159908 KB Partially correct
93 Partially correct 1438 ms 161120 KB Partially correct
94 Partially correct 1618 ms 160836 KB Partially correct
95 Partially correct 1349 ms 160520 KB Partially correct
96 Partially correct 3 ms 6236 KB Partially correct
97 Partially correct 29 ms 6124 KB Partially correct
98 Partially correct 26 ms 5980 KB Partially correct
99 Partially correct 29 ms 6132 KB Partially correct
100 Partially correct 18 ms 5976 KB Partially correct
101 Partially correct 20 ms 5980 KB Partially correct
102 Partially correct 10 ms 5976 KB Partially correct
103 Partially correct 1024 ms 158064 KB Partially correct
104 Partially correct 1572 ms 158348 KB Partially correct
105 Partially correct 1587 ms 158684 KB Partially correct
106 Partially correct 1605 ms 161236 KB Partially correct
107 Partially correct 133 ms 161484 KB Partially correct
108 Partially correct 827 ms 161108 KB Partially correct
109 Partially correct 972 ms 161744 KB Partially correct
110 Partially correct 1157 ms 160660 KB Partially correct
111 Partially correct 564 ms 159056 KB Partially correct
112 Partially correct 1362 ms 161316 KB Partially correct