Submission #295256

#	Time	Username	Problem	Language	Result	Execution time	Memory
295256		kdh9949	케이크 (JOI13_cake)	C++17	100 / 100	314 ms	105080 KiB

cake

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

namespace Seg {
  int sz;
  vint p;
  vll a, d;

  void i(int n) {
    for(sz = 1; sz < n; sz *= 2);
    p = vint(2 * sz);
    a = vll(sz + 1);
    a[sz] = ll(1e18);
    d = vll(2 * sz);
    for(int i = sz; i < 2 * sz; i++) p[i] = i - sz;
    for(int i = sz - 1; i; i--) p[i] = p[2 * i + 1];
  }

  void s(int x, ll v) {
    a[x] = v;
    for(x = (x + sz) / 2; x; x /= 2) {
      p[x] = (a[p[2 * x]] < a[p[2 * x + 1]] ? p[2 * x] : p[2 * x + 1]);
    }
  }

  int mn(int s, int e) {
    int r = sz;
    for(s += sz, e += sz; s <= e; s /= 2, e /= 2) {
      if(s & 1) { r = (a[r] > a[p[s]] ? p[s] : r); s++; }
      if(~e & 1) { r = (a[r] > a[p[e]] ? p[e] : r); e--; }
    }
    return r;
  }

  int gl(int x, ll v) {
    for(x += sz; ; x = (x - 1) / 2) if(a[p[x]] < v) break;
    for(; x < sz; ) {
      if(a[p[2 * x + 1]] < v) x = 2 * x + 1;
      else x = 2 * x;
    }
    return x - sz;
  }

  int gr(int x, ll v) {
    for(x += sz; ; x = (x + 1) / 2) if(a[p[x]] < v) break;
    for(; x < sz; ) {
      if(a[p[2 * x]] < v) x = 2 * x;
      else x = 2 * x + 1;
    }
    return x - sz;
  }

  void u(int s, int e, ll v) {
    for(s += sz, e += sz; s <= e; s /= 2, e /= 2) {
      if(s & 1) d[s++] += v;
      if(~e & 1) d[e--] += v;
    }
  }

  ll g(int x) {
    ll r = 0;
    for(x += sz; x; x /= 2) r += d[x];
    return r;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;

  vll v(3 * n), os(3 * n), es(3 * n);
  for(int i = 0; i < n; i++) {
    cin >> v[i];
    v[n + i] = v[2 * n + i] = v[i];
  }
  Seg::i(3 * n);
  for(int i = 0; i < 3 * n; i++) {
    Seg::s(i, v[i]);
    if(i) {
      os[i] = os[i - 1];
      es[i] = es[i - 1];
    }
    (i % 2 ? os[i] : es[i]) += v[i];
  }

  auto sum = [&](int s, int e, int turn, int dir) {
    turn ^= (dir ? e : s);
    return (turn & 1 ? os[e] - os[s - 1] : es[e] - es[s - 1]);
  };

  int mi = int(min_element(all(v)) - v.begin());
  vll ans(n);
  ans[mi] = v[mi];
  for(int s = n + mi - 1, e = n + mi + 1; e - s <= n; ) {
    if(v[s] < v[e]) { ans[mi] += sum(e, e, e - s - 1, 0); e++; }
    else { ans[mi] += sum(s, s, e - s - 1, 1); s--; }
  }

  function<void(int, int)> f = [&](int s, int e) {
    if(s > e) return;
    int x = Seg::mn(s, e);
    f(s, x - 1);
    f(x + 1, e);
    
    ll lv = sum(x, e, x - s, 0);
    ll rv = sum(s, x, e - x, 1);
    Seg::u(s, x - 1, lv);
    Seg::u(x + 1, e, rv);

    ll xans = v[x];
    if(x - s < e - x) {
      int nj = x + 1;
      for(int i = x - 1, j = x + 1; i >= s; i--, j = nj) {
        if(j <= e) nj = min(e + 1, Seg::gr(j, v[i]));
        xans += sum(j, nj - 1, j - i - 1, 0) + sum(i, i, nj - i - 1, 1);
      }
      xans += sum(nj, e, nj - s, 0);
    }
    else {
      int nj = x - 1;
      for(int i = x + 1, j = x - 1; i <= e; i++, j = nj) {
        if(j >= s) nj = max(s - 1, Seg::gl(j, v[i]));
        xans += sum(nj + 1, j, i - j - 1, 1) + sum(i, i, i - nj - 1, 0);
      }
      xans += sum(s, nj, e - nj, 1);
    }
    Seg::u(x, x, xans);
  };
  f(mi + 1, n + mi - 1);
  
  for(int i = mi + 1; i <= n + mi - 1; i++) ans[i % n] = Seg::g(i) + (n & 1 ? v[mi] : 0);
  for(int i = 0; i < n; i++) cout << ans[i] << '\n';
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90