Submission #295537

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

bulves

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const long long inf = 1e16;
long long pre[maxn];
long long aux[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;
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    scanf("%d %d", &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; } );
  segtree rmq (n, inf, [] (long long i, long long j) { return i < j ? i : j; } );
  int cnt = 0;
  for(int i = n; i >= 1; i--) {
    if(pre[i] > 0) {
      ++cnt;
      rmq.update(i, i, pre[i]);
    }
    else {
      --cnt;
      rmq.update(i, i, inf);
    }
    profit.update(i, i, cnt);
  }
  long long total = 0;
  while(pre[n] > total) {
    int id = profit.query(1, n).second;
    long long minVal = rmq.query(id, n).first;
    total += minVal;
    rmq.update(id, n, -minVal);
    aux[id] -= minVal;
    while(true) {
      auto var = rmq.query(1, n);
      if(var.first == 0) {
        rmq.update(var.second, var.second, inf);
        profit.update(1, var.second, -2);
      } else {
        break;
      }
    }
  }
  long long ans = 0;
  for(int i = 1; i <= n; i++) {
    aux[i] += aux[i - 1];
    ans += abs(pre[i] + aux[i]);
  }
  printf("%lld\n", ans);
}

Compilation message (stderr)

bulves.cpp: In function 'int main()':
bulves.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
bulves.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |     scanf("%d %d", &a[i], &b[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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