Submission #1060790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1060790	2024-08-15T22:47:39 Z	MilosMilutinovic	Tricks of the Trade (CEOI23_trade)	C++14	60 / 100	2141 ms	177344 KB

trade

#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(i, mid);
        } else if (best == res) {
          segs.emplace_back(i, 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	348 KB	Output is correct
2	Correct	1 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	1 ms	604 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	600 KB	Output is 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	Correct	1 ms	604 KB	Output is correct

Subtask #2

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	1 ms	604 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	604 KB	Output is correct
7	Correct	1 ms	600 KB	Output is 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	Correct	1 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	0 ms	348 KB	Output is correct
15	Correct	0 ms	604 KB	Output is correct
16	Correct	0 ms	604 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	1 ms	600 KB	Output is correct
20	Correct	1 ms	604 KB	Output is correct
21	Correct	1 ms	604 KB	Output is correct
22	Correct	2 ms	604 KB	Output is correct
23	Correct	4 ms	6100 KB	Output is correct
24	Correct	58 ms	4244 KB	Output is correct
25	Correct	164 ms	5980 KB	Output is correct
26	Correct	163 ms	4956 KB	Output is correct
27	Correct	844 ms	4624 KB	Output is correct
28	Correct	22 ms	4184 KB	Output is correct
29	Correct	12 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	1093 ms	158044 KB	Partially correct
3	Partially correct	1079 ms	156752 KB	Partially correct
4	Partially correct	1953 ms	157140 KB	Partially correct
5	Partially correct	2141 ms	157648 KB	Partially correct
6	Partially correct	1845 ms	157804 KB	Partially correct
7	Partially correct	2088 ms	157904 KB	Partially correct
8	Partially correct	1054 ms	156496 KB	Partially correct
9	Partially correct	1133 ms	156852 KB	Partially correct
10	Partially correct	1151 ms	157960 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	1093 ms	158044 KB	Partially correct
3	Partially correct	1079 ms	156752 KB	Partially correct
4	Partially correct	1953 ms	157140 KB	Partially correct
5	Partially correct	2141 ms	157648 KB	Partially correct
6	Partially correct	1845 ms	157804 KB	Partially correct
7	Partially correct	2088 ms	157904 KB	Partially correct
8	Partially correct	1054 ms	156496 KB	Partially correct
9	Partially correct	1133 ms	156852 KB	Partially correct
10	Partially correct	1151 ms	157960 KB	Partially correct
11	Correct	1 ms	348 KB	Output is correct
12	Partially correct	1090 ms	159304 KB	Partially correct
13	Partially correct	1048 ms	156500 KB	Partially correct
14	Partially correct	1822 ms	161284 KB	Partially correct
15	Partially correct	2092 ms	160252 KB	Partially correct
16	Partially correct	1664 ms	158748 KB	Partially correct
17	Partially correct	1984 ms	161860 KB	Partially correct
18	Partially correct	987 ms	157780 KB	Partially correct
19	Partially correct	1112 ms	157988 KB	Partially correct
20	Partially correct	1069 ms	159056 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	1 ms	604 KB	Output is correct
25	Correct	1 ms	604 KB	Output is correct
26	Correct	1 ms	604 KB	Output is 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	Correct	1 ms	604 KB	Output is correct
31	Partially correct	1116 ms	157760 KB	Partially correct
32	Partially correct	2071 ms	158968 KB	Partially correct
33	Partially correct	1971 ms	159212 KB	Partially correct
34	Partially correct	1674 ms	158928 KB	Partially correct
35	Partially correct	1478 ms	158668 KB	Partially correct
36	Partially correct	1669 ms	157892 KB	Partially correct
37	Partially correct	1410 ms	162660 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	1 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	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	600 KB	Output is 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	Correct	1 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	0 ms	348 KB	Output is correct
17	Correct	0 ms	604 KB	Output is correct
18	Correct	0 ms	604 KB	Output is correct
19	Correct	1 ms	604 KB	Output is correct
20	Correct	1 ms	604 KB	Output is correct
21	Correct	1 ms	600 KB	Output is correct
22	Correct	1 ms	604 KB	Output is correct
23	Correct	1 ms	604 KB	Output is correct
24	Correct	2 ms	604 KB	Output is correct
25	Correct	4 ms	6100 KB	Output is correct
26	Correct	58 ms	4244 KB	Output is correct
27	Correct	164 ms	5980 KB	Output is correct
28	Correct	163 ms	4956 KB	Output is correct
29	Correct	844 ms	4624 KB	Output is correct
30	Correct	22 ms	4184 KB	Output is correct
31	Correct	12 ms	5980 KB	Output is correct
32	Correct	1 ms	344 KB	Output is correct
33	Partially correct	1093 ms	158044 KB	Partially correct
34	Partially correct	1079 ms	156752 KB	Partially correct
35	Partially correct	1953 ms	157140 KB	Partially correct
36	Partially correct	2141 ms	157648 KB	Partially correct
37	Partially correct	1845 ms	157804 KB	Partially correct
38	Partially correct	2088 ms	157904 KB	Partially correct
39	Partially correct	1054 ms	156496 KB	Partially correct
40	Partially correct	1133 ms	156852 KB	Partially correct
41	Partially correct	1151 ms	157960 KB	Partially correct
42	Correct	1 ms	348 KB	Output is correct
43	Partially correct	1090 ms	159304 KB	Partially correct
44	Partially correct	1048 ms	156500 KB	Partially correct
45	Partially correct	1822 ms	161284 KB	Partially correct
46	Partially correct	2092 ms	160252 KB	Partially correct
47	Partially correct	1664 ms	158748 KB	Partially correct
48	Partially correct	1984 ms	161860 KB	Partially correct
49	Partially correct	987 ms	157780 KB	Partially correct
50	Partially correct	1112 ms	157988 KB	Partially correct
51	Partially correct	1069 ms	159056 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	1 ms	604 KB	Output is correct
56	Correct	1 ms	604 KB	Output is correct
57	Correct	1 ms	604 KB	Output is 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	Correct	1 ms	604 KB	Output is correct
62	Partially correct	1116 ms	157760 KB	Partially correct
63	Partially correct	2071 ms	158968 KB	Partially correct
64	Partially correct	1971 ms	159212 KB	Partially correct
65	Partially correct	1674 ms	158928 KB	Partially correct
66	Partially correct	1478 ms	158668 KB	Partially correct
67	Partially correct	1669 ms	157892 KB	Partially correct
68	Partially correct	1410 ms	162660 KB	Partially correct
69	Correct	1 ms	348 KB	Output is correct
70	Partially correct	1114 ms	159332 KB	Partially correct
71	Partially correct	1039 ms	157660 KB	Partially correct
72	Partially correct	1815 ms	158468 KB	Partially correct
73	Partially correct	1942 ms	160364 KB	Partially correct
74	Partially correct	1621 ms	160452 KB	Partially correct
75	Partially correct	1956 ms	161744 KB	Partially correct
76	Partially correct	956 ms	160668 KB	Partially correct
77	Partially correct	1070 ms	160592 KB	Partially correct
78	Partially correct	1085 ms	160464 KB	Partially correct
79	Correct	1 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	0 ms	604 KB	Output is correct
83	Correct	1 ms	604 KB	Output is correct
84	Correct	2 ms	604 KB	Output is 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	Correct	1 ms	604 KB	Output is correct
89	Partially correct	1056 ms	160680 KB	Partially correct
90	Partially correct	1942 ms	160208 KB	Partially correct
91	Partially correct	1862 ms	160424 KB	Partially correct
92	Partially correct	1609 ms	160300 KB	Partially correct
93	Partially correct	1462 ms	161332 KB	Partially correct
94	Partially correct	1621 ms	160832 KB	Partially correct
95	Partially correct	1362 ms	163688 KB	Partially correct
96	Correct	4 ms	7124 KB	Output is correct
97	Correct	56 ms	6132 KB	Output is correct
98	Correct	163 ms	6172 KB	Output is correct
99	Correct	160 ms	6176 KB	Output is correct
100	Correct	837 ms	6604 KB	Output is correct
101	Correct	20 ms	5976 KB	Output is correct
102	Correct	12 ms	5980 KB	Output is correct
103	Partially correct	1046 ms	158060 KB	Partially correct
104	Partially correct	1609 ms	158336 KB	Partially correct
105	Partially correct	1651 ms	159084 KB	Partially correct
106	Partially correct	1799 ms	159188 KB	Partially correct
107	Partially correct	159 ms	177344 KB	Partially correct
108	Partially correct	980 ms	161288 KB	Partially correct
109	Partially correct	1033 ms	167704 KB	Partially correct
110	Partially correct	1257 ms	161748 KB	Partially correct
111	Partially correct	619 ms	159056 KB	Partially correct
112	Partially correct	1359 ms	165068 KB	Partially correct