oj.uz

Submission #1060789

# Submission time Handle Problem Language Result Execution time Memory
1060789 2024-08-15T22:47:01 Z MilosMilutinovic Tricks of the Trade (CEOI23_trade) C++14
50 / 100
 2255 ms 173252 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);
        }
      } else if (v == best) {
        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 (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
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 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Partially correct 1 ms 604 KB Partially correct
7 Partially correct 1 ms 604 KB Partially correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Partially correct 1 ms 604 KB Partially 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 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Partially correct 1 ms 604 KB Partially correct
7 Partially correct 1 ms 604 KB Partially correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Partially correct 1 ms 604 KB Partially correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Partially correct 1 ms 604 KB Partially correct
18 Partially correct 1 ms 604 KB Partially correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 612 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Partially correct 1 ms 604 KB Partially correct
23 Correct 4 ms 7120 KB Output is correct
24 Partially correct 67 ms 5976 KB Partially correct
25 Partially correct 136 ms 6168 KB Partially correct
26 Partially correct 171 ms 5976 KB Partially correct
27 Correct 908 ms 6744 KB Output is correct
28 Correct 20 ms 5976 KB Output is correct
29 Correct 11 ms 5976 KB Output is correct

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Partially correct 1056 ms 159484 KB Partially correct
3 Partially correct 1020 ms 160596 KB Partially correct
4 Partially correct 1744 ms 159704 KB Partially correct
5 Partially correct 1904 ms 160212 KB Partially correct
6 Partially correct 1633 ms 161972 KB Partially correct
7 Partially correct 1945 ms 160212 KB Partially correct
8 Partially correct 969 ms 159292 KB Partially correct
9 Partially correct 1035 ms 159452 KB Partially correct
10 Partially correct 1089 ms 160496 KB Partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Partially correct 1056 ms 159484 KB Partially correct
3 Partially correct 1020 ms 160596 KB Partially correct
4 Partially correct 1744 ms 159704 KB Partially correct
5 Partially correct 1904 ms 160212 KB Partially correct
6 Partially correct 1633 ms 161972 KB Partially correct
7 Partially correct 1945 ms 160212 KB Partially correct
8 Partially correct 969 ms 159292 KB Partially correct
9 Partially correct 1035 ms 159452 KB Partially correct
10 Partially correct 1089 ms 160496 KB Partially correct
11 Correct 1 ms 344 KB Output is correct
12 Partially correct 1062 ms 160360 KB Partially correct
13 Partially correct 1002 ms 160828 KB Partially correct
14 Partially correct 1768 ms 159704 KB Partially correct
15 Partially correct 1914 ms 160548 KB Partially correct
16 Partially correct 1677 ms 161964 KB Partially correct
17 Partially correct 1931 ms 161744 KB Partially correct
18 Partially correct 952 ms 160824 KB Partially correct
19 Partially correct 1044 ms 160596 KB Partially correct
20 Partially correct 1012 ms 160468 KB Partially correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 604 KB Output is correct
25 Partially correct 1 ms 604 KB Partially correct
26 Partially correct 1 ms 604 KB Partially correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Partially correct 1 ms 604 KB Partially correct
31 Partially correct 1000 ms 161056 KB Partially correct
32 Partially correct 1990 ms 160364 KB Partially correct
33 Partially correct 1943 ms 161980 KB Partially correct
34 Partially correct 1769 ms 160324 KB Partially correct
35 Partially correct 1507 ms 158680 KB Partially correct
36 Partially correct 1683 ms 158124 KB Partially correct
37 Partially correct 1401 ms 162544 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 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 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Partially correct 1 ms 604 KB Partially correct
9 Partially correct 1 ms 604 KB Partially correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Partially correct 1 ms 604 KB Partially correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Partially correct 1 ms 604 KB Partially correct
20 Partially correct 1 ms 604 KB Partially correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 612 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Partially correct 1 ms 604 KB Partially correct
25 Correct 4 ms 7120 KB Output is correct
26 Partially correct 67 ms 5976 KB Partially correct
27 Partially correct 136 ms 6168 KB Partially correct
28 Partially correct 171 ms 5976 KB Partially correct
29 Correct 908 ms 6744 KB Output is correct
30 Correct 20 ms 5976 KB Output is correct
31 Correct 11 ms 5976 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Partially correct 1056 ms 159484 KB Partially correct
34 Partially correct 1020 ms 160596 KB Partially correct
35 Partially correct 1744 ms 159704 KB Partially correct
36 Partially correct 1904 ms 160212 KB Partially correct
37 Partially correct 1633 ms 161972 KB Partially correct
38 Partially correct 1945 ms 160212 KB Partially correct
39 Partially correct 969 ms 159292 KB Partially correct
40 Partially correct 1035 ms 159452 KB Partially correct
41 Partially correct 1089 ms 160496 KB Partially correct
42 Correct 1 ms 344 KB Output is correct
43 Partially correct 1062 ms 160360 KB Partially correct
44 Partially correct 1002 ms 160828 KB Partially correct
45 Partially correct 1768 ms 159704 KB Partially correct
46 Partially correct 1914 ms 160548 KB Partially correct
47 Partially correct 1677 ms 161964 KB Partially correct
48 Partially correct 1931 ms 161744 KB Partially correct
49 Partially correct 952 ms 160824 KB Partially correct
50 Partially correct 1044 ms 160596 KB Partially correct
51 Partially correct 1012 ms 160468 KB Partially correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 1 ms 604 KB Output is correct
55 Correct 0 ms 604 KB Output is correct
56 Partially correct 1 ms 604 KB Partially correct
57 Partially correct 1 ms 604 KB Partially correct
58 Correct 1 ms 604 KB Output is correct
59 Correct 1 ms 604 KB Output is correct
60 Correct 1 ms 604 KB Output is correct
61 Partially correct 1 ms 604 KB Partially correct
62 Partially correct 1000 ms 161056 KB Partially correct
63 Partially correct 1990 ms 160364 KB Partially correct
64 Partially correct 1943 ms 161980 KB Partially correct
65 Partially correct 1769 ms 160324 KB Partially correct
66 Partially correct 1507 ms 158680 KB Partially correct
67 Partially correct 1683 ms 158124 KB Partially correct
68 Partially correct 1401 ms 162544 KB Partially correct
69 Correct 0 ms 348 KB Output is correct
70 Partially correct 1123 ms 161880 KB Partially correct
71 Partially correct 1029 ms 160824 KB Partially correct
72 Partially correct 1804 ms 161488 KB Partially correct
73 Partially correct 2068 ms 160256 KB Partially correct
74 Partially correct 1653 ms 161748 KB Partially correct
75 Partially correct 2061 ms 161980 KB Partially correct
76 Partially correct 981 ms 159292 KB Partially correct
77 Partially correct 1055 ms 157984 KB Partially correct
78 Partially correct 1048 ms 160464 KB Partially correct
79 Correct 0 ms 348 KB Output is correct
80 Correct 0 ms 348 KB Output is correct
81 Correct 1 ms 604 KB Output is correct
82 Correct 1 ms 600 KB Output is correct
83 Partially correct 1 ms 604 KB Partially correct
84 Partially correct 1 ms 604 KB Partially correct
85 Correct 1 ms 604 KB Output is correct
86 Correct 1 ms 604 KB Output is correct
87 Correct 1 ms 604 KB Output is correct
88 Partially correct 1 ms 604 KB Partially correct
89 Partially correct 1054 ms 156588 KB Partially correct
90 Partially correct 2255 ms 157648 KB Partially correct
91 Partially correct 2027 ms 160840 KB Partially correct
92 Partially correct 1744 ms 157808 KB Partially correct
93 Partially correct 1487 ms 160296 KB Partially correct
94 Partially correct 1680 ms 157772 KB Partially correct
95 Partially correct 1430 ms 162216 KB Partially correct
96 Correct 4 ms 7124 KB Output is correct
97 Partially correct 68 ms 6156 KB Partially correct
98 Partially correct 131 ms 6404 KB Partially correct
99 Partially correct 172 ms 6140 KB Partially correct
100 Correct 1016 ms 5212 KB Output is correct
101 Correct 32 ms 4188 KB Output is correct
102 Correct 11 ms 4232 KB Output is correct
103 Partially correct 1179 ms 159316 KB Partially correct
104 Partially correct 1735 ms 157036 KB Partially correct
105 Partially correct 1784 ms 157652 KB Partially correct
106 Partially correct 1785 ms 157828 KB Partially correct
107 Partially correct 189 ms 173252 KB Partially correct
108 Partially correct 1002 ms 157144 KB Partially correct
109 Partially correct 1050 ms 165356 KB Partially correct
110 Partially correct 1266 ms 158888 KB Partially correct
111 Partially correct 626 ms 157740 KB Partially correct
112 Partially correct 1419 ms 162344 KB Partially correct