oj.uz

Submission #424096

# Submission time Handle Problem Language Result Execution time Memory
424096 2021-06-11T16:37:11 Z Mamnoon_Siam Cake 3 (JOI19_cake3) C++17
100 / 100
 745 ms 99616 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

const int N = 2e5 + 5;

struct node {
  ll sum;
  int cnt, l, r;
  node () {
    cnt = 0, sum = 0;
    l = 0, r = 0; // careful
  }
};
node t[N * 19];
int ptr = 0;
int n, m, root[N];
ll V[N], C[N];

void update(int& u, int b, int e, int pos, ll val) {
  t[++ptr] = t[u];
  t[u = ptr].sum += val;
  t[u].cnt++;
  if(b == e) return;
  int mid = (b + e) >> 1;
  if(pos <= mid)
    update(t[u].l, b, mid, pos, val);
  else
    update(t[u].r, mid+1, e, pos, val);
  // pull? no
}

ll largest_ksum(int u, int v, int b, int e, int k) { // [v] \ [u]
  // assumption: v.cnt - u.cnt >= m
  if(t[v].cnt - t[u].cnt == k) return t[v].sum - t[u].sum;
  // assumption:
  //    * v.cnt - u.cnt > m
  //    * b < e
  // if left half has >= m, then just return that result
  int mid = (b + e) >> 1;
  if(t[t[v].l].cnt - t[t[u].l].cnt >= k)
    return largest_ksum(t[u].l, t[v].l, b, mid, k);
  // otherwise left half has < m, take  that
  // and take the rest from right half
  else {
    ll ret = t[t[v].l].sum - t[t[u].l].sum;
    int took = t[t[v].l].cnt - t[t[u].l].cnt;
    return ret + largest_ksum(t[u].r, t[v].r, mid+1, e, k - took);
  }
}

ll cost(int l, int r) {
  return largest_ksum(root[l], root[r-1], 1, n, m-2) + V[l] + V[r] - 2*(C[r] - C[l]);
  // return largest_ksum(root[l-1], root[r], 1, n, m) - 2LL * (C[r] - C[l]);
}

ll ans = LLONG_MIN;

void solve(int l, int r, int b, int e) { // solve for [l, r] in search space [b, e]
  if(l > r) return;
  pair<ll,int> opt(LLONG_MIN, -1);
  int mid = (l + r) >> 1;
  for(int i = b; i <= min(e, mid-m+1); ++i) {
    opt = max(opt, {cost(i, mid), i});
  }
  assert(~opt.se);
  ans = max(ans, opt.fi);
  solve(l, mid-1, b, opt.se);
  solve(mid+1, r, opt.se, e);
}

int main(int argc, char const *argv[])
{
  cin.sync_with_stdio(0); cin.tie(0);
  cin.exceptions(cin.failbit);
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  cin >> n >> m;
  for(int i = 1; i <= n; ++i) {
    cin >> V[i] >> C[i];
  }
  vi p(n); iota(all(p), 1);
  sort(all(p), [](int i,int j){ return C[i] < C[j]; });
  {
    vi VV(n), CC(n);
    for(int i = 0; i < n; ++i) {
      VV[i] = (int)V[p[i]];
      CC[i] = (int)C[p[i]];
    }
    for(int i = 1; i <= n; ++i) {
      V[i] = VV[i-1];
      C[i] = CC[i-1];
    }
  }
  debug(vi(C+1, C+1+n));
  debug(vi(V+1, V+1+n));
  vi v_ord(n); iota(all(v_ord), 1);
  sort(all(v_ord), [](int i, int j){ return V[i] > V[j]; });
  vi v_rank(n+1);
  for(int i = 0; i < n; ++i) {
    v_rank[v_ord[i]] = i+1;
  }
  debug(v_ord);
  debug(vi(v_rank.begin() + 1, v_rank.end()));
  root[0] = 0;
  for(int i = 1; i <= n; ++i) {
    root[i] = root[i-1];
    update(root[i], 1, n, v_rank[i], V[i]);
  }
  solve(m, n, 1, n);
  cout << ans << endl;
  return 0;
}
/*
* use std::array instead of std::vector, if u can
* overflow?
* array bounds
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 89548 KB Output is correct
2 Correct 43 ms 89540 KB Output is correct
3 Correct 46 ms 89556 KB Output is correct
4 Correct 42 ms 89444 KB Output is correct
5 Correct 42 ms 89528 KB Output is correct
6 Correct 41 ms 89440 KB Output is correct
7 Correct 43 ms 89468 KB Output is correct
8 Correct 43 ms 89504 KB Output is correct
9 Correct 46 ms 89472 KB Output is correct
10 Correct 42 ms 89556 KB Output is correct
11 Correct 44 ms 89512 KB Output is correct
12 Correct 42 ms 89536 KB Output is correct
13 Correct 42 ms 89560 KB Output is correct
14 Correct 42 ms 89500 KB Output is correct
15 Correct 41 ms 89472 KB Output is correct
16 Correct 43 ms 89500 KB Output is correct
17 Correct 41 ms 89548 KB Output is correct
18 Correct 43 ms 89508 KB Output is correct
19 Correct 42 ms 89476 KB Output is correct
20 Correct 43 ms 89472 KB Output is correct
21 Correct 42 ms 89428 KB Output is correct
22 Correct 42 ms 89540 KB Output is correct
23 Correct 42 ms 89540 KB Output is correct
24 Correct 42 ms 89496 KB Output is correct
25 Correct 41 ms 89432 KB Output is correct
26 Correct 42 ms 89432 KB Output is correct
27 Correct 42 ms 89552 KB Output is correct
28 Correct 48 ms 89516 KB Output is correct
29 Correct 43 ms 89448 KB Output is correct
30 Correct 44 ms 89540 KB Output is correct
31 Correct 42 ms 89544 KB Output is correct
32 Correct 42 ms 89472 KB Output is correct
33 Correct 41 ms 89540 KB Output is correct
34 Correct 42 ms 89552 KB Output is correct
35 Correct 44 ms 89468 KB Output is correct
36 Correct 42 ms 89492 KB Output is correct
37 Correct 42 ms 89540 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 89548 KB Output is correct
2 Correct 43 ms 89540 KB Output is correct
3 Correct 46 ms 89556 KB Output is correct
4 Correct 42 ms 89444 KB Output is correct
5 Correct 42 ms 89528 KB Output is correct
6 Correct 41 ms 89440 KB Output is correct
7 Correct 43 ms 89468 KB Output is correct
8 Correct 43 ms 89504 KB Output is correct
9 Correct 46 ms 89472 KB Output is correct
10 Correct 42 ms 89556 KB Output is correct
11 Correct 44 ms 89512 KB Output is correct
12 Correct 42 ms 89536 KB Output is correct
13 Correct 42 ms 89560 KB Output is correct
14 Correct 42 ms 89500 KB Output is correct
15 Correct 41 ms 89472 KB Output is correct
16 Correct 43 ms 89500 KB Output is correct
17 Correct 41 ms 89548 KB Output is correct
18 Correct 43 ms 89508 KB Output is correct
19 Correct 42 ms 89476 KB Output is correct
20 Correct 43 ms 89472 KB Output is correct
21 Correct 42 ms 89428 KB Output is correct
22 Correct 42 ms 89540 KB Output is correct
23 Correct 42 ms 89540 KB Output is correct
24 Correct 42 ms 89496 KB Output is correct
25 Correct 41 ms 89432 KB Output is correct
26 Correct 42 ms 89432 KB Output is correct
27 Correct 42 ms 89552 KB Output is correct
28 Correct 48 ms 89516 KB Output is correct
29 Correct 43 ms 89448 KB Output is correct
30 Correct 44 ms 89540 KB Output is correct
31 Correct 42 ms 89544 KB Output is correct
32 Correct 42 ms 89472 KB Output is correct
33 Correct 41 ms 89540 KB Output is correct
34 Correct 42 ms 89552 KB Output is correct
35 Correct 44 ms 89468 KB Output is correct
36 Correct 42 ms 89492 KB Output is correct
37 Correct 42 ms 89540 KB Output is correct
38 Correct 52 ms 89584 KB Output is correct
39 Correct 44 ms 89612 KB Output is correct
40 Correct 44 ms 89520 KB Output is correct
41 Correct 44 ms 89576 KB Output is correct
42 Correct 43 ms 89548 KB Output is correct
43 Correct 46 ms 89500 KB Output is correct
44 Correct 50 ms 89540 KB Output is correct
45 Correct 44 ms 89540 KB Output is correct
46 Correct 43 ms 89540 KB Output is correct
47 Correct 45 ms 89592 KB Output is correct
48 Correct 45 ms 89496 KB Output is correct
49 Correct 44 ms 89532 KB Output is correct
50 Correct 45 ms 89612 KB Output is correct
51 Correct 43 ms 89520 KB Output is correct
52 Correct 44 ms 89548 KB Output is correct
53 Correct 44 ms 89732 KB Output is correct
54 Correct 45 ms 89712 KB Output is correct
55 Correct 43 ms 89548 KB Output is correct
56 Correct 43 ms 89504 KB Output is correct
57 Correct 43 ms 89556 KB Output is correct
58 Correct 46 ms 89540 KB Output is correct
59 Correct 43 ms 89740 KB Output is correct
60 Correct 43 ms 89616 KB Output is correct
61 Correct 44 ms 89584 KB Output is correct
62 Correct 43 ms 89548 KB Output is correct
63 Correct 43 ms 89528 KB Output is correct
64 Correct 43 ms 89612 KB Output is correct
65 Correct 44 ms 89604 KB Output is correct
66 Correct 44 ms 89548 KB Output is correct
67 Correct 45 ms 89588 KB Output is correct
68 Correct 43 ms 89552 KB Output is correct
69 Correct 45 ms 89520 KB Output is correct
70 Correct 44 ms 89504 KB Output is correct
71 Correct 43 ms 89628 KB Output is correct
72 Correct 42 ms 89556 KB Output is correct
73 Correct 45 ms 89540 KB Output is correct
74 Correct 42 ms 89540 KB Output is correct

Subtask #3
76.0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 89548 KB Output is correct
2 Correct 43 ms 89540 KB Output is correct
3 Correct 46 ms 89556 KB Output is correct
4 Correct 42 ms 89444 KB Output is correct
5 Correct 42 ms 89528 KB Output is correct
6 Correct 41 ms 89440 KB Output is correct
7 Correct 43 ms 89468 KB Output is correct
8 Correct 43 ms 89504 KB Output is correct
9 Correct 46 ms 89472 KB Output is correct
10 Correct 42 ms 89556 KB Output is correct
11 Correct 44 ms 89512 KB Output is correct
12 Correct 42 ms 89536 KB Output is correct
13 Correct 42 ms 89560 KB Output is correct
14 Correct 42 ms 89500 KB Output is correct
15 Correct 41 ms 89472 KB Output is correct
16 Correct 43 ms 89500 KB Output is correct
17 Correct 41 ms 89548 KB Output is correct
18 Correct 43 ms 89508 KB Output is correct
19 Correct 42 ms 89476 KB Output is correct
20 Correct 43 ms 89472 KB Output is correct
21 Correct 42 ms 89428 KB Output is correct
22 Correct 42 ms 89540 KB Output is correct
23 Correct 42 ms 89540 KB Output is correct
24 Correct 42 ms 89496 KB Output is correct
25 Correct 41 ms 89432 KB Output is correct
26 Correct 42 ms 89432 KB Output is correct
27 Correct 42 ms 89552 KB Output is correct
28 Correct 48 ms 89516 KB Output is correct
29 Correct 43 ms 89448 KB Output is correct
30 Correct 44 ms 89540 KB Output is correct
31 Correct 42 ms 89544 KB Output is correct
32 Correct 42 ms 89472 KB Output is correct
33 Correct 41 ms 89540 KB Output is correct
34 Correct 42 ms 89552 KB Output is correct
35 Correct 44 ms 89468 KB Output is correct
36 Correct 42 ms 89492 KB Output is correct
37 Correct 42 ms 89540 KB Output is correct
38 Correct 52 ms 89584 KB Output is correct
39 Correct 44 ms 89612 KB Output is correct
40 Correct 44 ms 89520 KB Output is correct
41 Correct 44 ms 89576 KB Output is correct
42 Correct 43 ms 89548 KB Output is correct
43 Correct 46 ms 89500 KB Output is correct
44 Correct 50 ms 89540 KB Output is correct
45 Correct 44 ms 89540 KB Output is correct
46 Correct 43 ms 89540 KB Output is correct
47 Correct 45 ms 89592 KB Output is correct
48 Correct 45 ms 89496 KB Output is correct
49 Correct 44 ms 89532 KB Output is correct
50 Correct 45 ms 89612 KB Output is correct
51 Correct 43 ms 89520 KB Output is correct
52 Correct 44 ms 89548 KB Output is correct
53 Correct 44 ms 89732 KB Output is correct
54 Correct 45 ms 89712 KB Output is correct
55 Correct 43 ms 89548 KB Output is correct
56 Correct 43 ms 89504 KB Output is correct
57 Correct 43 ms 89556 KB Output is correct
58 Correct 46 ms 89540 KB Output is correct
59 Correct 43 ms 89740 KB Output is correct
60 Correct 43 ms 89616 KB Output is correct
61 Correct 44 ms 89584 KB Output is correct
62 Correct 43 ms 89548 KB Output is correct
63 Correct 43 ms 89528 KB Output is correct
64 Correct 43 ms 89612 KB Output is correct
65 Correct 44 ms 89604 KB Output is correct
66 Correct 44 ms 89548 KB Output is correct
67 Correct 45 ms 89588 KB Output is correct
68 Correct 43 ms 89552 KB Output is correct
69 Correct 45 ms 89520 KB Output is correct
70 Correct 44 ms 89504 KB Output is correct
71 Correct 43 ms 89628 KB Output is correct
72 Correct 42 ms 89556 KB Output is correct
73 Correct 45 ms 89540 KB Output is correct
74 Correct 42 ms 89540 KB Output is correct
75 Correct 691 ms 95396 KB Output is correct
76 Correct 745 ms 98748 KB Output is correct
77 Correct 599 ms 99024 KB Output is correct
78 Correct 620 ms 99176 KB Output is correct
79 Correct 215 ms 99256 KB Output is correct
80 Correct 254 ms 99008 KB Output is correct
81 Correct 536 ms 98436 KB Output is correct
82 Correct 657 ms 98464 KB Output is correct
83 Correct 613 ms 98740 KB Output is correct
84 Correct 682 ms 98604 KB Output is correct
85 Correct 559 ms 98392 KB Output is correct
86 Correct 369 ms 97972 KB Output is correct
87 Correct 353 ms 98024 KB Output is correct
88 Correct 486 ms 97848 KB Output is correct
89 Correct 469 ms 98432 KB Output is correct
90 Correct 372 ms 98764 KB Output is correct
91 Correct 289 ms 98000 KB Output is correct
92 Correct 279 ms 97964 KB Output is correct
93 Correct 332 ms 98348 KB Output is correct
94 Correct 277 ms 98608 KB Output is correct
95 Correct 357 ms 98760 KB Output is correct
96 Correct 301 ms 98200 KB Output is correct
97 Correct 331 ms 98732 KB Output is correct
98 Correct 359 ms 98672 KB Output is correct
99 Correct 301 ms 98700 KB Output is correct
100 Correct 248 ms 98216 KB Output is correct
101 Correct 258 ms 98108 KB Output is correct
102 Correct 697 ms 98064 KB Output is correct
103 Correct 551 ms 97992 KB Output is correct
104 Correct 694 ms 98456 KB Output is correct
105 Correct 489 ms 98452 KB Output is correct
106 Correct 516 ms 98652 KB Output is correct
107 Correct 501 ms 98332 KB Output is correct
108 Correct 595 ms 98856 KB Output is correct
109 Correct 509 ms 99392 KB Output is correct
110 Correct 276 ms 97608 KB Output is correct
111 Correct 374 ms 97708 KB Output is correct
112 Correct 614 ms 97348 KB Output is correct
113 Correct 219 ms 99616 KB Output is correct