Submission #1040517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040517		abczz	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	4444 KiB

cake3

#include <iostream>
#include <array>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

ll n, m, f, mx, s, cnt, cl, cr;
map <ll, ll> mp;
vector <ll> V;
array<ll, 2> A[200000];
queue <array<ll, 4>> Q[2];

struct SegTree{
  ll st[800000], tot[800000];
  void update(ll id, ll l, ll r, ll q) {
    if (l == r) {
      st[id] ^= V[l], tot[id] ^= 1;
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q);
    else update(id*2+1, mid+1, r, q);
    st[id] = st[id*2] + st[id*2+1];
    tot[id] = tot[id*2] + tot[id*2+1];
  }
  ll query(ll id, ll l, ll r, ll z) {
    if (l == r) {
      z -= tot[id];
      if (z == 0) return st[id];
      else return -1e18;
    }
    ll mid = (l+r)/2;
    if (tot[id*2+1] >= z) return query(id*2+1, mid+1, r, z);
    else return st[id*2+1] + query(id*2, l, mid, z-tot[id*2+1]);
  }
}ST;
void solve(ll l, ll r, ll ql, ll qr) {
  ll mid = (l+r)/2;
  while (cr+1 < max(mid, ql)) {
    ++cr;
    ST.update(1, 0, n-1, A[cr][0]);
  }
  while (cl < mid) {
    ST.update(1, 0, n-1, A[cl][0]);
    ++cl;
  }
  ll opt = -1, optid = max(mid, ql), res;
  //cout << cl << " " << cr << "*" << mid << " " << ql << " " << ST.st[1] << endl;
  for (int i=max(mid, ql); i<=qr; ++i) {
    ST.update(1, 0, n-1, A[i][0]);
    res = ST.query(1, 0, n-1, m) - 2*A[i][1] + 2*A[mid][1];
    //cout << mid << " " << i << " " << ST.query(1, 0, n-1, m) << endl;
    if (opt < res) {
      opt = res;
      optid = i;
    }
  }
  for (int i=max(mid, ql); i<=qr; ++i) {
    ST.update(1, 0, n-1, A[i][0]);
  }
  f = max(f, opt);
  if (l < mid) Q[1].push({l, mid-1, ql, optid});
  if (mid < r) Q[1].push({mid+1, r, optid, qr});
}
void bfs() {
  while (!Q[0].empty()) {
    cl = 0, cr = -1;
    while (!Q[0].empty()) {
      auto [l, r, ql, qr] = Q[0].front();
      Q[0].pop();
      solve(l, r, ql, qr);
    }
    swap(Q[0], Q[1]);
    while (cr+1 < n) {
      ++cr;
      ST.update(1, 0, n-1, A[cr][0]);
    }
    while (cl < n) {
      ST.update(1, 0, n-1, A[cl][0]);
      ++cl;
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i=0; i<2; ++i) {
    while (!Q[i].empty()) Q[i].pop();
  }
  V.clear();
  f = -1e18;
  for (int i=0; i<n; ++i) {
    cin >> A[i][0] >> A[i][1];
    ++mp[A[i][0]];
  }
  for (auto &[x, y] : mp) {
    V.push_back(x);
    y = cnt++;
  }
  sort(A, A+n, [](auto a, auto b) {
    return a[1] < b[1];
  });
  for (int i=0; i<n; ++i) {
    A[i][0] = mp[A[i][0]];
  }
  Q[0].push({0, n-m, m-1, n-1});
  bfs();
  cout << f << '\n';
}

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