oj.uz

Submission #295526

# Submission time Handle Problem Language Result Execution time Memory
295526 2020-09-09T18:06:52 Z Bruteforceman Potatoes and fertilizers (LMIO19_bulves) C++11
64 / 100
 1000 ms 59020 KB 
#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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 62 ms 6136 KB Output is correct
5 Correct 121 ms 11900 KB Output is correct
6 Correct 435 ms 31224 KB Output is correct
7 Correct 894 ms 59000 KB Output is correct
8 Correct 761 ms 59020 KB Output is correct
9 Correct 741 ms 58764 KB Output is correct
10 Correct 544 ms 57208 KB Output is correct
11 Correct 542 ms 57208 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 62 ms 6136 KB Output is correct
5 Correct 121 ms 11900 KB Output is correct
6 Correct 435 ms 31224 KB Output is correct
7 Correct 894 ms 59000 KB Output is correct
8 Correct 761 ms 59020 KB Output is correct
9 Correct 741 ms 58764 KB Output is correct
10 Correct 544 ms 57208 KB Output is correct
11 Correct 542 ms 57208 KB Output is correct
12 Correct 214 ms 15736 KB Output is correct
13 Correct 535 ms 37112 KB Output is correct
14 Correct 888 ms 59000 KB Output is correct
15 Correct 762 ms 58872 KB Output is correct
16 Correct 721 ms 58872 KB Output is correct
17 Correct 629 ms 57208 KB Output is correct
18 Correct 3 ms 640 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 10 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 12 ms 768 KB Output is correct
13 Correct 12 ms 768 KB Output is correct
14 Correct 19 ms 768 KB Output is correct
15 Correct 9 ms 768 KB Output is correct
16 Correct 9 ms 640 KB Output is correct
17 Correct 6 ms 768 KB Output is correct
18 Correct 3 ms 640 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 10 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 62 ms 6136 KB Output is correct
12 Correct 121 ms 11900 KB Output is correct
13 Correct 435 ms 31224 KB Output is correct
14 Correct 894 ms 59000 KB Output is correct
15 Correct 761 ms 59020 KB Output is correct
16 Correct 741 ms 58764 KB Output is correct
17 Correct 544 ms 57208 KB Output is correct
18 Correct 542 ms 57208 KB Output is correct
19 Correct 214 ms 15736 KB Output is correct
20 Correct 535 ms 37112 KB Output is correct
21 Correct 888 ms 59000 KB Output is correct
22 Correct 762 ms 58872 KB Output is correct
23 Correct 721 ms 58872 KB Output is correct
24 Correct 629 ms 57208 KB Output is correct
25 Correct 7 ms 640 KB Output is correct
26 Correct 12 ms 768 KB Output is correct
27 Correct 12 ms 768 KB Output is correct
28 Correct 19 ms 768 KB Output is correct
29 Correct 9 ms 768 KB Output is correct
30 Correct 9 ms 640 KB Output is correct
31 Correct 6 ms 768 KB Output is correct
32 Execution timed out 1090 ms 15736 KB Time limit exceeded
33 Halted 0 ms 0 KB -