Submission #680778

#	Time	Username	Problem	Language	Result	Execution time	Memory
680778		keta_tsimakuridze	Cake 3 (JOI19_cake3)	C++17	100 / 100	2203 ms	25520 KiB

cake3

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
const ll inf = 1e18; // !
int m, OPE = 0;
multiset<int> s, s_;
struct _ {
    int v, c;
} x[N];
int t[4 * N], pos[N], id[N], c[4 * N];

void upd(int u, int id, int l, int r, int v) {
    if(l == r) {
        t[u] += v * pos[id];
        c[u] += v;
        return;
    }
    int mid = (l + r) / 2;
    if(id <= mid) upd(2 * u, id, l, mid, v);
    else upd(2 * u + 1, id, mid + 1, r, v);
    t[u] = t[2 * u] + t[2 * u + 1];
    c[u] = c[2 * u] + c[2 * u + 1];
}
int get(int u, int k, int l, int r) {
    if(l == r) return pos[l] * k;
    int mid = (l + r) / 2;
    if(c[2 * u + 1] >= k) return get(2 * u + 1, k, mid + 1, r);
    return t[2 * u + 1] + get(2 * u, k - c[2 * u + 1], l, mid);
}
bool cmp(_ x, _ y) {
    return x.c < y.c;
}
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n >> m;
    vector<int> y;
    for(int i = 1; i <= n; i++) {
        cin >> x[i].v >> x[i].c;
        y.push_back(x[i].v);
    }
    sort(y.begin(), y.end());
    y.erase(unique(y.begin(), y.end()), y.end());
    sort(x + 1, x + n + 1, cmp);
    for(int i = 1; i <= n; i++) id[i] = lower_bound(y.begin(), y.end(), x[i].v) - y.begin() + 1;
    for(int i = 0; i + 1 <= y.size(); i++) pos[i + 1] = y[i];
    queue< pair<pii, pii> > st;

    st.push({{m, n}, {1, n}});
    int L = 0, R = 0, F = 0;
    ll ans = -inf;
    while(st.size()) {
        int l = st.front().f.f, r = st.front().f.s, optl = st.front().s.f, optr = st.front().s.s;
        st.pop();
        int mid = (l + r) / 2;
        if(R > mid) {
            L = R = 0;
            for(int i = 1; i <= 4 * n; i++) t[i] = c[i] = 0;
            assert(OPE <= 20);
        }
//        cout << L << " __ _ __" << " " << R << endl;
        // optl .. min(mid - m + 1, optr) gvawyobs

        while(R < mid) {
            ++R;
            upd(1, id[R], 1, n, 1);
        }
        while(L < min(optr, mid - m + 1)) {
           if(L) upd(1, id[L], 1, n, -1);
            ++L;
        }
        assert(L == min(optr, mid - m + 1));
        assert(R == mid);
        ll X = get(1, m, 1, n) - (x[mid].c - x[min(optr, mid - m + 1)].c) * 2, opt = min(optr, mid - m + 1);
        for(int i = min(optr, mid - m + 1) - 1; i >= optl; i--) {
            upd(1, id[i], 1, n, 1);
            int xx = get(1, m, 1, n);
            if(xx - (x[mid].c - x[i].c) * 2 > X) opt = i, X = xx - (x[mid].c - x[i].c) * 2;
        }
        L = optl;
        ans = max(ans, X);

        if(l < mid) st.push({{l, mid - 1},{optl, opt}});
        if(mid < r) st.push({{mid + 1, r}, {opt, optr}});
    }

    cout << ans;


 }

Compilation message (stderr)

cake3.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main(){
      | ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:51:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i + 1 <= y.size(); i++) pos[i + 1] = y[i];
      |                    ~~~~~~^~~~~~~~~~~
cake3.cpp:55:23: warning: unused variable 'F' [-Wunused-variable]
   55 |     int L = 0, R = 0, F = 0;
      |                       ^

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