結果

問題 No.860 買い物
コンテスト
ユーザー pekempey
提出日時 2019-08-09 23:20:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,993 bytes
コンパイル時間 2,018 ms
コンパイル使用メモリ 180,572 KB
実行使用メモリ 9,088 KB
最終ジャッジ日時 2024-07-19 15:52:11
合計ジャッジ時間 4,346 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)

using namespace std;
using ll = long long;

struct add_max {
  int N;
  vector<long long> dat;
  vector<long long> lazy;

  add_max(int n) {
    N = 1;
    while (N < n) N *= 2;
    dat.resize(N * 2);
    lazy.resize(N * 2);
  }

  void apply(int k, long long v) {
    dat[k] += v;
    lazy[k] += v;
  }

  void push(int k) {
    apply(k*2+0, lazy[k]);
    apply(k*2+1, lazy[k]);
    lazy[k] = 0;
  }

  void pull(int k) {
    dat[k] = min(dat[k*2], dat[k*2+1]);
  }

  void update(int a, int b, long long v, int k = 1, int l = 0, int r = -1) {
    if (r == -1) r = N;
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      apply(k, v);
      return;
    }
    push(k);
    int m = (l + r) / 2;
    update(a, b, v, k*2+0, l, m);
    update(a, b, v, k*2+1, m, r);
    pull(k);
  }

  long long query(int a, int b, int k = 1, int l = 0, int r = -1) {
    if (r == -1) r = N;
    if (r <= a || b <= l) return 1e18;
    if (a <= l && r <= b) return dat[k];
    int m = (l + r) / 2;
    long long vl = query(a, b, k*2+0, l, m);
    long long vr = query(a, b, k*2+1, m, r);
    return min(vl, vr);
  }
};


int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N; cin >> N;
  vector<ll> C(N + 1), D(N + 1); rep(i, N) cin >> C[i] >> D[i];
  add_max seg(N + 1);
  vector<pair<int, ll>> stk;
  stk.push_back({-1, -1e18});
  ll sumC = 0;
  ll sumD = -D[0];
  for (int i = 1; i <= N; i++) {
    sumC += C[i - 1];
    sumD += D[i - 1];
    seg.update(i - 1, i, C[i - 1]);
    int j = i - 1;
    while (stk.back().second >= C[i - 1]) {
      seg.update(stk.back().first, j, -stk.back().second);
      seg.update(stk.back().first, j, C[i - 1]);
      j = stk.back().first;
      stk.pop_back();
    }
    stk.emplace_back(i - 1, C[i - 1]);
    seg.update(i, i + 1, seg.query(0, i) - D[i]);
  }
  cout << seg.query(N, N + 1) + sumC + sumD << endl;
}
0