Submission #625471

#	Time	Username	Problem	Language	Result	Execution time	Memory
625471		Do_you_copy	Cake 3 (JOI19_cake3)	C++17	100 / 100	572 ms	151228 KiB

cake3

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 2e5 + 10;
int n, m;
int node_cnt = 1;

vector <int> val[maxN * 4];
vector <ll> sum[maxN * 4];
vector <int> b;
ll pre[maxN];

struct TNode{
    int l, r;
    int lp, rp;
    TNode(){
         l = r = lp = rp = 0;
    }
    TNode(int _l, int _r){
        l = _l;
        r = _r;
    }
};
TNode wt[maxN * 4];

void build(int id, auto i, auto j, int l, int r){
    wt[id].l = l;
    wt[id].r = r;
    if (l == r){
        return;
    }
    val[id].pb(0);
    sum[id].pb(0);
    int mid = (l + r - (l + r < 0)) / 2;
    int maxx = l;
    int minn = r;
    for (auto it = i; it != j; ++it){
        val[id].pb(val[id].back() + (*it <= mid));
        sum[id].pb(sum[id].back() + *it * (*it <= mid));
        if (*it <= mid) maxx = max(maxx, *it);
        else minn = min(minn, *it);
    }
    auto p = stable_partition(i, j,[=](const auto &w){
        return w <= mid;
    });
    wt[id].lp = ++node_cnt;
    wt[id].rp = ++node_cnt;
    build(wt[id].lp, i, p, l, maxx);
    build(wt[id].rp, p, j, minn, r);
}

ll get(int k, int i, int j){
    bool flag = 0; if (k == 3 && i == 2 && j == 5) flag = 1;
    if (k == 0) return 0;
    --i;
    ll res = 0;
    int id = 1;
    int l = wt[id].l, r = wt[id].r;
    while (l < r){
        int mid = (l + r) / 2;
        if (k <= val[id][j] - val[id][i]){
            i = val[id][i];
            j = val[id][j];
            id = wt[id].lp;
        }
        else{
            res += sum[id][j] - sum[id][i];
            k -= val[id][j] - val[id][i];
            i -= val[id][i];
            j -= val[id][j];
            id = wt[id].rp;
        }
        l = wt[id].l, r = wt[id].r;
    }
    res += k * l;
    return res;
}

struct TCake{
    int v, c;
    bool operator < (const TCake &other) const{
        return c < other.c;
    }
};
TCake a[maxN];

ll ans = -1e15;

//IOI 2014 Holiday?
void DnC(int l, int r, int from, int to){
    if (l > r) return;
    int mid = (l + r) / 2;
    ll tem = -1e15, pos = 0;
    for (int i = max(from, mid + m - 1) ; i <= to; ++i){
        ll q = - get(m, mid, i) + 2 * (a[mid].c - a[i].c);
        if (tem < q){
            pos = i;
            tem = q;
        }
    }
    ans = max(ans, tem);
    assert(pos != 0);
	DnC(l, mid - 1, from, pos);
	DnC(mid + 1, r, pos, to);
}

void Init(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].v >> a[i].c;
    }
    sort(a + 1, a + n + 1);
    b.resize(n + 1);
    for (int i = 1; i <= n; ++i){
        b[i] = -a[i].v;
    }
    build(1, b.begin() + 1, b.end(), *min_element(b.begin() + 1, b.end()),
           *max_element(b.begin() + 1, b.end()));
    DnC(1, n - m + 1, m, n);
    cout << ans;
}

#define debu
#define taskname "test"
signed main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        #ifdef debug
        freopen(taskname".out", "w", stdout);
        #endif
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << 1000 * double(clock()) / CLOCKS_PER_SEC;
        #ifndef debug
        cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n";
        #endif
    }
}

Compilation message (stderr)

cake3.cpp:50:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   50 | void build(int id, auto i, auto j, int l, int r){
      |                    ^~~~
cake3.cpp:50:28: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   50 | void build(int id, auto i, auto j, int l, int r){
      |                            ^~~~
cake3.cpp: In function 'll get(long long int, long long int, long long int)':
cake3.cpp:84:13: warning: unused variable 'mid' [-Wunused-variable]
   84 |         int mid = (l + r) / 2;
      |             ^~~
cake3.cpp:77:10: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
   77 |     bool flag = 0; if (k == 3 && i == 2 && j == 5) flag = 1;
      |          ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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