제출 #953973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953973		Pring	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	2392 KiB

cake3

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 200005, LG = 35, MXC = 1000000005;
int n, m;
pii p[MXN];
int ans;

namespace PSMG {
#define mid ((l + r) >> 1)
    int val[MXN * LG], cnt[MXN * LG], L[MXN * LG], R[MXN * LG], nc;
    vector<int> rt;

    int new_node(int ref) {
        val[nc] = val[ref];
        cnt[nc] = cnt[ref];
        L[nc] = L[ref];
        R[nc] = R[ref];
        return nc++;
    }

    int modify(int id, int l, int r, int p, int v) {
        id = new_node(id);
        if (l + 1 == r) {
            val[id] += p * v;
            cnt[id] += v;
            return id;
        }
        if (p < mid) L[id] = modify(L[id], l, mid, p, v);
        else R[id] = modify(R[id], mid, r, p, v);
        val[id] = val[L[id]] + val[R[id]];
        cnt[id] = cnt[L[id]] + cnt[R[id]];
        return id;
    }

    void init() {
        nc = 2;
        rt.push_back(1);
        FOR(i, 0, n) {
            rt.push_back(modify(rt.back(), 0, MXC, p[i].sc, 1));
        }
    }

    int query(int idl, int idr, int l, int r, int bnd) {
        debug(l, r, bnd, cnt[idl], cnt[idr]);
        if (bnd == cnt[idr] - cnt[idl]) {
            debug(val[idl], val[idr]);
            return val[idr] - val[idl];
        }
        int rcnt = cnt[R[idr]] - cnt[R[idl]];
        if (rcnt >= bnd) return query(R[idl], R[idr], mid, r, bnd);
        return val[R[idr]] - val[R[idl]] + query(L[idl], L[idr], l, mid, bnd - rcnt);
    }

    int calc(int l, int r) {
        // debug(l, r);
        return query(rt[l], rt[r], 0, MXC, m - 2);
    }
#undef mid
}

pii calc(int id, int l, int r) {
    pii ans = mp(0LL, -1LL);
    FOR(i, l, r + 1) {
        if (id - i + 1 < m) continue;
        ans = max(ans, mp(PSMG::calc(i + 1, id) + p[id].sc - 2 * p[id].fs + p[i].sc + 2 * p[i].fs, i));
        debug(i + 1, id, ans.fs);
    }
    return ans;
}

void solve(int l, int r, int kl, int kr) {
    if (l == r) return;
    debug(l, r, kl, kr);
    int mid = (l + r) >> 1;
    auto [val, k] = calc(mid, kl, kr);
    debug(mid, val, k);
    ans = max(ans, val);
    solve(l, mid, kl, k);
    solve(mid + 1, r, k, kr);
}

void miku() {
    cin >> n >> m;
    FOR(i, 0, n) cin >> p[i].sc >> p[i].fs;
    sort(p, p + n);
    PSMG::init();
    // cout << PSMG::calc(3, 4) << '\n';
    solve(0, n, 0, n - 1);
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In function 'long long int PSMG::query(long long int, long long int, long long int, long long int, long long int)':
cake3.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
cake3.cpp:62:9: note: in expansion of macro 'debug'
   62 |         debug(l, r, bnd, cnt[idl], cnt[idr]);
      |         ^~~~~
cake3.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
cake3.cpp:64:13: note: in expansion of macro 'debug'
   64 |             debug(val[idl], val[idr]);
      |             ^~~~~
cake3.cpp: In function 'pii calc(long long int, long long int, long long int)':
cake3.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
cake3.cpp:84:9: note: in expansion of macro 'debug'
   84 |         debug(i + 1, id, ans.fs);
      |         ^~~~~
cake3.cpp: In function 'void solve(long long int, long long int, long long int, long long int)':
cake3.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
cake3.cpp:91:5: note: in expansion of macro 'debug'
   91 |     debug(l, r, kl, kr);
      |     ^~~~~
cake3.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
cake3.cpp:94:5: note: in expansion of macro 'debug'
   94 |     debug(mid, val, k);
      |     ^~~~~

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