Submission #295526

#	Time	Username	Problem	Language	Result	Execution time	Memory
295526		Bruteforceman	Potatoes and fertilizers (LMIO19_bulves)	C++11	64 / 100	1090 ms	59020 KiB

bulves

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const long long inf = 1e16;
long long pre[maxn];
int a[maxn], b[maxn];

struct node {
  long long val, lazy;
  int index;
  node () { val = lazy = index = 0; }
  node (long long val) : val(val) { lazy = index = 0; }
  void add(long long x) {
    val += x;
    lazy += x;
  }
};
struct segtree {
  vector <node> t;
  int size;
  long long useless;
  function <long long(long long, long long)> func;
  void merge(node &cur, node l, node r) {
    cur.val = func(l.val, r.val);
    if(cur.val == r.val) cur.index = r.index;
    if(cur.val == l.val) cur.index = l.index;
  }
  void pushdown(int c) {
    int l = c << 1;
    int r = l + 1;
    t[l].add(t[c].lazy);
    t[r].add(t[c].lazy);
    t[c].lazy = 0;
  }
  void build(int c, int b, int e) {
    t[c].val = 0;
    t[c].lazy = 0;
    if(b == e) {
      t[c].index = b;
      return ;
    }
    int m = (b + e) >> 1;
    int l = c << 1;
    int r = l + 1;
    build(l, b, m);
    build(r, m + 1, e);
    merge(t[c], t[l], t[r]);
  }
  segtree(int size, long long useless, function <long long(long long, long long)> func) : size(size), useless(useless), func(func) {
    t.resize(4 * size + 1);
    build(1, 1, size);
  }
  void update(int x, int y, long long val, int c, int b, int e) {
    if(x <= b && e <= y) {
      t[c].add(val);
      return ;
    }
    if(y < b || e < x) return ;
    pushdown(c);
    int m = (b + e) >> 1;
    int l = c << 1;
    int r = l + 1;
    update(x, y, val, l, b, m);
    update(x, y, val, r, m + 1, e);
    merge(t[c], t[l], t[r]);
  }
  node query(int x, int y, int c, int b, int e) {
    if(x <= b && e <= y) return t[c];
    if(y < b || e < x) return node(useless);
    pushdown(c);
    int m = (b + e) >> 1;
    int l = c << 1;
    int r = l + 1;
    node ans;
    merge(ans, query(x, y, l, b, m), query(x, y, r, m + 1, e));
    return ans;
  }
  void update(int x, int y, long long val) {
    update(x, y, val, 1, 1, size);
  }
  pair <long long, int> query(int x, int y) {
    node ans = query(x, y, 1, 1, size);
    return make_pair(ans.val, ans.index);
  }
};

int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
    pre[i] = pre[i - 1] + a[i] - b[i];
  }
  segtree profit (n, -inf, [] (long long i, long long j) { return i < j ? j : i; } );
  int cnt = 0;
  for(int i = n; i >= 1; i--) {
    if(pre[i] > 0) ++cnt;
    else --cnt;
    profit.update(i, i, cnt);
  }
  while(pre[n] > 0) {
    int id = profit.query(1, n).second;
    long long minVal = pre[n];
    for(int i = id; i <= n; i++) {
      if(pre[i] > 0) minVal = min(minVal, pre[i]);
    }
    for(int i = id; i <= n; i++) {
      pre[i] -= minVal;
      if(pre[i] == 0) {
        profit.update(1, i, -2);
      }
    }
  }
  long long ans = 0;
  for(int i = 1; i <= n; i++) ans += abs(pre[i]);
  cout << ans << endl;
}

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 0 / 36