Submission #466517

#	Time	Username	Problem	Language	Result	Execution time	Memory
466517		jhwest2	Cake 3 (JOI19_cake3)	C++14	24 / 100	4067 ms	122028 KiB

cake3

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pint;

const int M = 2e5 + 10;
const lint INF = 4e18 + 10;

lint n, m, ans, A[M], B[M], D[M];
pair<lint, lint> X[M];

struct Pst {
    struct Node {
        lint cnt, val, l, r;
        Node() = default;
    } T[30 * M];
    int size = 0, rt = 0, R[M];

    int new_node() { return ++size; }
    void init(int lo = 1, int hi = n, int idx = 0) {
        if (lo == hi) return;
        init(lo, lo + hi >> 1, T[idx].l = new_node());
        init(1 + (lo + hi >> 1), hi, T[idx].r = new_node());
    }
    void update(int a, lint x) {
        R[++rt] = new_node();
        _update(a, x, 1, n, R[rt - 1], R[rt]);
    }
    void _update(int a, lint x, int lo, int hi, int idx, int jdx) {
        if (lo == hi) {
            T[jdx].val = T[idx].val + x;
            T[jdx].cnt = T[idx].cnt + 1;
            return;
        }
        int m = lo + hi >> 1;
        if (a <= m) {
            _update(a, x, lo, m, T[idx].l, T[jdx].l = new_node());
            T[jdx].r = T[idx].r;
        }
        else {
            _update(a, x, m + 1, hi, T[idx].r, T[jdx].r = new_node());
            T[jdx].l = T[idx].l;
        }
        T[jdx].val = T[T[jdx].l].val + T[T[jdx].r].val;
        T[jdx].cnt = T[T[jdx].l].cnt + T[T[jdx].r].cnt;
    }
    lint query(int a, int b) {
        int lo = 1, hi = rt;
        while (lo < hi) {
            int mid = lo + hi + 1 >> 1;
            if (cnt_query(a, b, 1, n, R[mid]) > m) hi = mid - 1;
            else lo = mid;
        }
        return sum_query(a, b, 1, n, R[lo]);
    }
    lint cnt_query(int a, int b, int lo, int hi, int idx) {
        if (b < lo || a > hi) return 0;
        if (a <= lo && hi <= b) return T[idx].cnt;
        return cnt_query(a, b, lo, lo + hi >> 1, T[idx].l) +
            cnt_query(a, b, 1 + (lo + hi >> 1), hi, T[idx].r);
    }
    lint sum_query(int a, int b, int lo, int hi, int idx) {
        if (b < lo || a > hi) return 0;
        if (a <= lo && hi <= b) return T[idx].val;
        return sum_query(a, b, lo, lo + hi >> 1, T[idx].l) +
            sum_query(a, b, 1 + (lo + hi >> 1), hi, T[idx].r);
    }
} S;
void solve(lint l, lint r, lint lo, lint hi) {
    if (l > r) return;
    if (lo == hi) {
        for (int i = l; i <= r; i++) {
            D[i] = lo;
        }
        return;
    }
    lint mid = l + r >> 1, mx = -INF;
    for (int i = max(lo, mid + m - 1); i <= hi; i++) {
        lint x = S.query(mid, i) - 2 * (B[i] - B[mid]);
        if (x > mx) mx = x, D[mid] = i;
    }
    solve(l, mid - 1, lo, D[mid]);
    solve(mid + 1, r, D[mid], hi);
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> X[i].va >> X[i].vb;
    }
    sort(X + 1, X + n + 1, [&](auto a, auto b) {
        return tie(a.vb, a.va) < tie(b.vb, b.va);
        });
    for (int i = 1; i <= n; i++) {
        tie(A[i], B[i]) = X[i];
    }
    vector<pint> V;
    for (int i = 1; i <= n; i++) {
        V.emplace_back(A[i], i);
    }
    sort(V.rbegin(), V.rend());
    for (auto [a, b] : V) S.update(b, a);   

    solve(1, n - m + 1, m, n);

    lint ans = -INF;
    for (int i = 1; i <= n; i++) {
        if (D[i] - i + 1 < m) continue;
        ans = max(ans, S.query(i, D[i]) - 2 * (B[D[i]] - B[i]));
    }
    cout << ans;
}

Compilation message (stderr)

cake3.cpp: In member function 'void Pst::init(int, int, int)':
cake3.cpp:27:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         init(lo, lo + hi >> 1, T[idx].l = new_node());
      |                  ~~~^~~~
cake3.cpp:28:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         init(1 + (lo + hi >> 1), hi, T[idx].r = new_node());
      |                   ~~~^~~~
cake3.cpp: In member function 'void Pst::_update(int, lint, int, int, int, int)':
cake3.cpp:40:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int m = lo + hi >> 1;
      |                 ~~~^~~~
cake3.cpp: In member function 'lint Pst::query(int, int)':
cake3.cpp:55:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |             int mid = lo + hi + 1 >> 1;
      |                       ~~~~~~~~^~~
cake3.cpp: In member function 'lint Pst::cnt_query(int, int, int, int, int)':
cake3.cpp:64:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         return cnt_query(a, b, lo, lo + hi >> 1, T[idx].l) +
      |                                    ~~~^~~~
cake3.cpp:65:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |             cnt_query(a, b, 1 + (lo + hi >> 1), hi, T[idx].r);
      |                                  ~~~^~~~
cake3.cpp: In member function 'lint Pst::sum_query(int, int, int, int, int)':
cake3.cpp:70:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         return sum_query(a, b, lo, lo + hi >> 1, T[idx].l) +
      |                                    ~~~^~~~
cake3.cpp:71:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |             sum_query(a, b, 1 + (lo + hi >> 1), hi, T[idx].r);
      |                                  ~~~^~~~
cake3.cpp: In function 'void solve(lint, lint, lint, lint)':
cake3.cpp:82:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     lint mid = l + r >> 1, mx = -INF;
      |                ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:107:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |     for (auto [a, b] : V) S.update(b, a);
      |               ^

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 0 / 76