Submission #604302

#	Time	Username	Problem	Language	Result	Execution time	Memory
604302		lunchbox	Feast (NOI19_feast)	C++17	100 / 100	815 ms	210980 KiB

feast

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

template<class T, class F>
T last_true(T lower, T upper, const F& f) {
  lower--;
  assert(lower <= upper);
  while (lower < upper) {
    T t = lower + (upper - lower + 1) / 2;

    if (f(t))
      lower = t;
    else
      upper = t - 1;
  }
  return lower;
}

const int N = 300000, N_ = 1 << 19;

#define int long long

array<int, 3> add(const array<int, 3> &l, const array<int, 3> &r) {
  assert(l[2] + 1 == r[1]);
  return { l[0] + r[0], l[1], r[2] };
}
 
struct T {
  array<int, 3> pref[2], suff[2], ans[2], sum[2];
  int empty;
 
  T() {
    for (int i = 0; i < 2; i++)
      pref[i] = suff[i] = ans[i] = sum[i] = { 0, 0, 0 };
    empty = 1;
  }
  void init(int i, int x) {
    sum[0] = { x, i, i }, sum[1] = { -x, i, i };
    if (x >= 0) {
      pref[0] = suff[0] = { +x, i, i };
      pref[1] = { 0, i, i - 1 }, suff[1] = { 0, i + 1, i };
    } else {
      pref[1] = suff[1] = {-x, i, i};
      pref[0] = { 0, i, i - 1 }, suff[0] = { 0, i + 1, i };
    }
    ans[0] = pref[0], ans[1] = pref[1];
    empty = 0;
  }
  void flip() {
    swap(pref[0], pref[1]);
    swap(suff[0], suff[1]);
    swap(ans[0], ans[1]);
    swap(sum[0], sum[1]);
  }
  friend T add(const T &l, const T &r) {
    T k = T();
 
    if (l.empty)
      return r;
    if (r.empty)
      return l;
    k.sum[0] = add(l.sum[0], r.sum[0]);
    k.pref[0] = max(l.pref[0], add(l.sum[0], r.pref[0]));
    k.suff[0] = max(r.suff[0], add(l.suff[0], r.sum[0]));
    k.ans[0] = max({ l.ans[0], r.ans[0], add(l.suff[0], r.pref[0]) });
    k.sum[1] = add(l.sum[1], r.sum[1]);
    k.pref[1] = max(l.pref[1], add(l.sum[1], r.pref[1]));
    k.suff[1] = max(r.suff[1], add(l.suff[1], r.sum[1]));
    k.ans[1] = max({ l.ans[1], r.ans[1], add(l.suff[1], r.pref[1]) });
    k.empty = 0;
    return k;
  }
} st[N_ * 2];
 
int lz[N_ * 2], n_;
 
void put(int k, int l, int r) {
  st[k].flip();
  if (l != r)
    lz[k] ^= 1;
}
 
void pus(int k, int l, int r) {
  if (lz[k]) {
    int m = (l + r) / 2;
 
    put(k << 1 | 0, l, m), put(k << 1 | 1, m + 1, r);
    lz[k] = 0;
  }
}
 
void pul(int k, int, int) {
  st[k] = add(st[k << 1 | 0], st[k << 1 | 1]);
}
 
T query(int ql, int qr, int k = 1, int l = 0, int r = n_ - 1) {
  if (ql > r || qr < l)
    return T();
  else if (ql <= l && qr >= r)
    return st[k];
  else {
    int m = (l + r) / 2;
 
    pus(k, l, r);
    return add(query(ql, qr, k << 1 | 0, l, m), query(ql, qr, k << 1 | 1, m + 1, r));
  }
}
 
void update1(int i, int x, int k = 1, int l = 0, int r = n_ - 1) {
  if (l == r)
    st[k].init(i, x);
  else {
    int m = (l + r) / 2;
 
    pus(k, l, r);
    if (i <= m)
      update1(i, x, k << 1 | 0, l, m);
    else
      update1(i, x, k << 1 | 1, m + 1, r);
    pul(k, l, r);
  }
}
 
void update2(int ql, int qr, int k = 1, int l = 0, int r = n_ - 1) {
  if (ql > r || qr < l)
    return;
  else if (ql <= l && qr >= r)
    put(k, l, r);
  else {
    int m = (l + r) / 2;
 
    pus(k, l, r);
    update2(ql, qr, k << 1 | 0, l, m), update2(ql, qr, k << 1 | 1, m + 1, r);
    pul(k, l, r);
  }
}

signed main() {
  int n, k;
  scanf("%lld%lld", &n, &k);
  n_ = 1;
  while (n_ < n)
    n_ <<= 1;
  for (int i = 0; i < n; i++) {
    int a;
    scanf("%lld", &a);
    update1(i, a);
  }
  int sum = 0;
  for (int i = 0; i < k; i++) {
    auto t = query(0, n - 1).ans[0];
    
    if (t[0] == 0)
      break;
    // printf("got %d\n", t[0]);
    sum += t[0];
    update2(t[1], t[2]);
  }
  printf("%lld\n", sum);
  return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |   scanf("%lld%lld", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
feast.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |     scanf("%lld", &a);
      |     ~~~~~^~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29