oj.uz

Submission #1060787

# Submission time Handle Problem Language Result Execution time Memory
1060787 2024-08-15T22:43:43 Z MilosMilutinovic Tricks of the Trade (CEOI23_trade) C++14
50 / 100
 6024 ms 162016 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;
  }
  for (auto& p : segs) {
    assert(Calc(p.first, p.second) == res);
  }
  vector<int> seq(n, 0);
  vector<int> f(n, -1);
  for (int l = 0; l < n; l++) {
    for (int r = l + k - 1; r < n; r++) {
      if (Calc(l, r) != res) {
        continue;
      }
      if (f[r] == -1) {
        f[r] = l;
      } else {
        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;
        }
      }
    }
  }
  int border = -1;
  for (int i = 0; i < n; i++) {
    if (f[i] == -1) {
      continue;
    }
    if (f[i] < border) {
      assert(false);
      border = f[i];
    }
  }
  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
5.0 / 10.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 2 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Partially correct 6 ms 604 KB Partially correct
7 Partially correct 4 ms 604 KB Partially correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Partially correct 5 ms 600 KB Partially correct

Subtask #2
5.0 / 10.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 2 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Partially correct 6 ms 604 KB Partially correct
7 Partially correct 4 ms 604 KB Partially correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Partially correct 5 ms 600 KB Partially correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Partially correct 6 ms 604 KB Partially correct
18 Partially correct 6 ms 600 KB Partially correct
19 Correct 3 ms 600 KB Output is correct
20 Correct 4 ms 612 KB Output is correct
21 Correct 5 ms 604 KB Output is correct
22 Partially correct 5 ms 604 KB Partially correct
23 Correct 3 ms 6236 KB Output is correct
24 Partially correct 5284 ms 6168 KB Partially correct
25 Partially correct 4342 ms 5976 KB Partially correct
26 Partially correct 5889 ms 5980 KB Partially correct
27 Correct 2071 ms 6236 KB Output is correct
28 Correct 5737 ms 6144 KB Output is correct
29 Correct 1467 ms 5980 KB Output is correct

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Partially correct 1058 ms 160408 KB Partially correct
3 Partially correct 1002 ms 160592 KB Partially correct
4 Partially correct 1732 ms 159060 KB Partially correct
5 Partially correct 1913 ms 161236 KB Partially correct
6 Partially correct 1689 ms 159744 KB Partially correct
7 Partially correct 1951 ms 160824 KB Partially correct
8 Partially correct 949 ms 160596 KB Partially correct
9 Partially correct 1057 ms 159312 KB Partially correct
10 Partially correct 1045 ms 160300 KB Partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Partially correct 1058 ms 160408 KB Partially correct
3 Partially correct 1002 ms 160592 KB Partially correct
4 Partially correct 1732 ms 159060 KB Partially correct
5 Partially correct 1913 ms 161236 KB Partially correct
6 Partially correct 1689 ms 159744 KB Partially correct
7 Partially correct 1951 ms 160824 KB Partially correct
8 Partially correct 949 ms 160596 KB Partially correct
9 Partially correct 1057 ms 159312 KB Partially correct
10 Partially correct 1045 ms 160300 KB Partially correct
11 Correct 0 ms 348 KB Output is correct
12 Partially correct 1050 ms 162016 KB Partially correct
13 Partially correct 982 ms 160680 KB Partially correct
14 Partially correct 1715 ms 160828 KB Partially correct
15 Partially correct 1862 ms 159816 KB Partially correct
16 Partially correct 1724 ms 159672 KB Partially correct
17 Partially correct 1975 ms 159056 KB Partially correct
18 Partially correct 948 ms 159056 KB Partially correct
19 Partially correct 1082 ms 159316 KB Partially correct
20 Partially correct 1022 ms 161852 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 608 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Partially correct 6 ms 348 KB Partially correct
26 Partially correct 5 ms 604 KB Partially correct
27 Correct 4 ms 856 KB Output is correct
28 Correct 4 ms 604 KB Output is correct
29 Correct 5 ms 604 KB Output is correct
30 Partially correct 5 ms 604 KB Partially correct
31 Partially correct 998 ms 159300 KB Partially correct
32 Partially correct 2004 ms 159824 KB Partially correct
33 Partially correct 1884 ms 159704 KB Partially correct
34 Partially correct 1623 ms 159820 KB Partially correct
35 Partially correct 1546 ms 161176 KB Partially correct
36 Partially correct 1629 ms 159104 KB Partially correct
37 Partially correct 1405 ms 160464 KB Partially correct

Subtask #5
25.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 344 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 Partially correct 6 ms 604 KB Partially correct
9 Partially correct 4 ms 604 KB Partially correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 4 ms 604 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Partially correct 5 ms 600 KB Partially correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Partially correct 6 ms 604 KB Partially correct
20 Partially correct 6 ms 600 KB Partially correct
21 Correct 3 ms 600 KB Output is correct
22 Correct 4 ms 612 KB Output is correct
23 Correct 5 ms 604 KB Output is correct
24 Partially correct 5 ms 604 KB Partially correct
25 Correct 3 ms 6236 KB Output is correct
26 Partially correct 5284 ms 6168 KB Partially correct
27 Partially correct 4342 ms 5976 KB Partially correct
28 Partially correct 5889 ms 5980 KB Partially correct
29 Correct 2071 ms 6236 KB Output is correct
30 Correct 5737 ms 6144 KB Output is correct
31 Correct 1467 ms 5980 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Partially correct 1058 ms 160408 KB Partially correct
34 Partially correct 1002 ms 160592 KB Partially correct
35 Partially correct 1732 ms 159060 KB Partially correct
36 Partially correct 1913 ms 161236 KB Partially correct
37 Partially correct 1689 ms 159744 KB Partially correct
38 Partially correct 1951 ms 160824 KB Partially correct
39 Partially correct 949 ms 160596 KB Partially correct
40 Partially correct 1057 ms 159312 KB Partially correct
41 Partially correct 1045 ms 160300 KB Partially correct
42 Correct 0 ms 348 KB Output is correct
43 Partially correct 1050 ms 162016 KB Partially correct
44 Partially correct 982 ms 160680 KB Partially correct
45 Partially correct 1715 ms 160828 KB Partially correct
46 Partially correct 1862 ms 159816 KB Partially correct
47 Partially correct 1724 ms 159672 KB Partially correct
48 Partially correct 1975 ms 159056 KB Partially correct
49 Partially correct 948 ms 159056 KB Partially correct
50 Partially correct 1082 ms 159316 KB Partially correct
51 Partially correct 1022 ms 161852 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 608 KB Output is correct
55 Correct 0 ms 604 KB Output is correct
56 Partially correct 6 ms 348 KB Partially correct
57 Partially correct 5 ms 604 KB Partially correct
58 Correct 4 ms 856 KB Output is correct
59 Correct 4 ms 604 KB Output is correct
60 Correct 5 ms 604 KB Output is correct
61 Partially correct 5 ms 604 KB Partially correct
62 Partially correct 998 ms 159300 KB Partially correct
63 Partially correct 2004 ms 159824 KB Partially correct
64 Partially correct 1884 ms 159704 KB Partially correct
65 Partially correct 1623 ms 159820 KB Partially correct
66 Partially correct 1546 ms 161176 KB Partially correct
67 Partially correct 1629 ms 159104 KB Partially correct
68 Partially correct 1405 ms 160464 KB Partially correct
69 Correct 0 ms 344 KB Output is correct
70 Partially correct 1112 ms 161860 KB Partially correct
71 Partially correct 997 ms 160828 KB Partially correct
72 Partially correct 1724 ms 160848 KB Partially correct
73 Partially correct 1941 ms 159912 KB Partially correct
74 Partially correct 1638 ms 159704 KB Partially correct
75 Partially correct 1926 ms 160592 KB Partially correct
76 Partially correct 990 ms 159312 KB Partially correct
77 Partially correct 1030 ms 160824 KB Partially correct
78 Partially correct 1012 ms 160464 KB Partially correct
79 Correct 0 ms 600 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 Partially correct 6 ms 612 KB Partially correct
84 Partially correct 4 ms 612 KB Partially correct
85 Correct 3 ms 604 KB Output is correct
86 Correct 4 ms 604 KB Output is correct
87 Correct 5 ms 604 KB Output is correct
88 Partially correct 5 ms 600 KB Partially correct
89 Partially correct 1004 ms 160824 KB Partially correct
90 Partially correct 1982 ms 159704 KB Partially correct
91 Partially correct 1897 ms 161240 KB Partially correct
92 Partially correct 1658 ms 159704 KB Partially correct
93 Partially correct 1474 ms 159568 KB Partially correct
94 Partially correct 1697 ms 160832 KB Partially correct
95 Partially correct 1353 ms 162008 KB Partially correct
96 Correct 4 ms 6236 KB Output is correct
97 Partially correct 5300 ms 6164 KB Partially correct
98 Partially correct 4376 ms 5976 KB Partially correct
99 Partially correct 6024 ms 6192 KB Partially correct
100 Correct 2023 ms 6236 KB Output is correct
101 Correct 5806 ms 6148 KB Output is correct
102 Correct 1462 ms 5976 KB Output is correct
103 Partially correct 1037 ms 158036 KB Partially correct
104 Partially correct 1602 ms 158344 KB Partially correct
105 Partially correct 1677 ms 159700 KB Partially correct
106 Partially correct 1631 ms 161424 KB Partially correct
107 Partially correct 120 ms 161232 KB Partially correct
108 Partially correct 914 ms 161152 KB Partially correct
109 Partially correct 966 ms 160468 KB Partially correct
110 Partially correct 1278 ms 159312 KB Partially correct
111 Partially correct 568 ms 159276 KB Partially correct
112 Partially correct 1398 ms 160004 KB Partially correct