oj.uz

Submission #694136

# Submission time Handle Problem Language Result Execution time Memory
694136 2023-02-03T22:40:22 Z erray Ants and Sugar (JOI22_sugar) C++17
42 / 100
 1243 ms 47888 KB 
// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

  struct node {
    //0 merge
    //1 max
    array<array<long long, 2>, 2> x{};
    array<long long, 2> tag{};
    void modify(int type, long long d) {
      if (type == 0) {
        //start max
        x[1][0] += d, x[1][1] += d;
        tag[type] += d;
      } else if (type == 1) {
        //end max
        x[0][1] += d, x[1][1] += d;
        tag[type] += d;      
      } else if (type == 2) {
        //start merge
        x[0][0] += d, x[0][1] += d; 
      } else if (type == 3) {
        //end merge
        x[0][0] += d, x[1][0] += d;      
      } else {
        //whole 
        x[0][0] += d, x[0][1] += d, x[1][0] += d, x[1][1] += d;
      }
    } 
  };
  node operator+(node l, node r) {
    l.x[1][1] = max(0LL, l.x[1][1]);
    r.x[1][1] = max(0LL, r.x[1][1]);
    node res;
    res.x[0][0] = max(l.x[0][1] + r.x[1][0], l.x[0][0] + r.x[0][0]);
    res.x[1][1] = max(l.x[1][1] + r.x[1][1], l.x[1][0] + r.x[0][1]);
    res.x[0][1] = max(l.x[0][1] + r.x[1][1], l.x[0][0] + r.x[0][1]);
    res.x[1][0] = max(r.x[1][0] + l.x[1][1], l.x[1][0] + r.x[0][0]);
    return res;
  }

struct SegTree {
  int n;
  vector<node> tree;
  #define def int mid = (l + r) >> 1, rv = v + ((mid - l + 1) << 1)
  void push(int v, int l, int r) {
    def;
    for (int i = 0; i < 2; ++i) {
      if (tree[v].tag[i] != 0) {
        tree[v + 1].modify(i, tree[v].tag[i]);
        tree[rv].modify(i, tree[v].tag[i]);        
        tree[v].tag[i] = 0;
      }
    }
  }
  void modify(int v, int l, int r, int ll, int rr, int type, int x) {
    if (l >= ll && rr >= r) {
      tree[v].modify(type, x);
      debug(v, l, tree[v].x);
      return;
    }        
    def;
    push(v, l, r);
    //debug(v, v + 1, rv);
    if (ll <= mid) {
      modify(v + 1, l, mid, ll, rr, type, x);
    }
    if (mid < rr) {
      modify(rv, mid + 1, r, ll, rr, type, x);
    }
    tree[v] = tree[v + 1] + tree[rv];
    debug(v, l, r, tree[v].x);  
  }
  SegTree(int _n) : n(_n) {
    tree.resize((n << 1) - 1);
  }
  long long get() {
    return max(0LL, tree[0].x[1][1]);
  }
  void modify(int l, int r, int type, int x) {
     assert(0 <= l && l <= r && r < n && 0 <= type && type < 4);
     debug(l, r, type, x);
     modify(0, 0, n - 1, l, r, type, x);
  }
  void modify(int p, int x) {
    assert(0 <= p && p < n);
    debug(p, x);
    modify(0, 0, n - 1, p, p, 4, x);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int Q, L;
  cin >> Q >> L;
  vector<int> T(Q), X(Q), A(Q);
  for (int i = 0; i < Q; ++i) {
    cin >> T[i] >> X[i] >> A[i];
  }
  debug(X);
  vector<int> cords;
  for (int i = 0; i < Q; ++i) {
    if (T[i] == 1) {
      cords.push_back(X[i]);
    }
  }
  sort(cords.begin(), cords.end());
  int s = int(unique(cords.begin(), cords.end()) - cords.begin());
  cords.resize(s);
  if (s == 0) {
    for (int i = 0; i < Q; ++i) {
      cout << 0;
    }
    return 0;
  }
  if (s == 1) {
    long long V = 0;
    long long U = 0;
    for (int i = 0; i < Q; ++i) {
      if (T[i] == 1) {
        V += A[i];
      } else if (abs(cords[0] - X[i]) <= L) {
        U += A[i];
      }
      cout << min(V, U) << '\n';
    }
    return 0;
  }
  auto LB = [&](int x) {
    return int(lower_bound(cords.begin(), cords.end(), x) - cords.begin());
  };
  debug(cords);

  SegTree st(s);
  long long total = 0;
  for (int q = 0; q < Q; ++q) {
    debug(q, total);
    if (T[q] == 1) {
      total += A[q]; 
      st.modify(LB(X[q]), A[q]);
    } else {
      int id = LB(X[q]);
      debug(id, A[q]);
      if (id < s && cords[id] == X[q]) {
        st.modify(LB(X[q]), -A[q]);
      } else if (id == s || (id > 0 && X[q] <= cords[id - 1] + L))  {
        st.modify(id - 1, id - 1, 3, -A[q]);
      } else {
        st.modify(id, id, 2, -A[q]);        
      }
      {
        int l = LB(X[q] - L);
        int r = LB(X[q]) - 1;
        debug(l, r);
        if (l <= r) {
          st.modify(l, r, 1, -A[q]);   
        }
      }
      {
         int r = LB(X[q] + L + 1) - 1;
         int l = LB(X[q] + 1);
         debug(l, r);
         if (l <= r) {
           st.modify(l, r, 0, -A[q]);
         }
      }
    }
    debug(total, st.get());
    cout << total - st.get() << '\n';
  }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 529 ms 28084 KB Output is correct
5 Correct 297 ms 22964 KB Output is correct
6 Correct 626 ms 32676 KB Output is correct
7 Correct 295 ms 23116 KB Output is correct
8 Correct 792 ms 38620 KB Output is correct
9 Correct 632 ms 47868 KB Output is correct
10 Correct 767 ms 38520 KB Output is correct
11 Correct 636 ms 47888 KB Output is correct
12 Correct 268 ms 19848 KB Output is correct
13 Correct 392 ms 27404 KB Output is correct
14 Correct 658 ms 44384 KB Output is correct
15 Correct 641 ms 44544 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 277 ms 19920 KB Output is correct
3 Correct 440 ms 27364 KB Output is correct
4 Correct 634 ms 44408 KB Output is correct
5 Correct 657 ms 44364 KB Output is correct
6 Correct 568 ms 32180 KB Output is correct
7 Correct 31 ms 3056 KB Output is correct
8 Correct 300 ms 17100 KB Output is correct
9 Correct 481 ms 24776 KB Output is correct
10 Correct 812 ms 45624 KB Output is correct
11 Correct 880 ms 45576 KB Output is correct
12 Correct 842 ms 45596 KB Output is correct
13 Correct 764 ms 45616 KB Output is correct
14 Correct 785 ms 45736 KB Output is correct
15 Correct 656 ms 45348 KB Output is correct
16 Correct 741 ms 45624 KB Output is correct
17 Correct 966 ms 45864 KB Output is correct
18 Correct 1116 ms 45740 KB Output is correct
19 Correct 1148 ms 45972 KB Output is correct
20 Correct 1135 ms 45688 KB Output is correct
21 Correct 1206 ms 45664 KB Output is correct
22 Correct 1243 ms 45732 KB Output is correct
23 Correct 1151 ms 45716 KB Output is correct
24 Correct 993 ms 45744 KB Output is correct
25 Correct 1030 ms 45832 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -