Submission #897878

#	Time	Username	Problem	Language	Result	Execution time	Memory
897878		cadmiumsky	Two Dishes (JOI19_dishes)	C++17	74 / 100	3908 ms	235500 KiB

dishes

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<ll,ll>;
using tii = tuple<int,int,int>;

// default constructorul trebuie sa fie identitate
// sorry it had to be this way
template<typename Mono, typename Lazy>
struct AINT {
  const Mono ID_M = Mono();
  const Lazy ID_L = Lazy();
  struct Node {
    Mono val;
    Lazy lazy;
    Node(Mono a, Lazy b): val(a), lazy(b) {;}
    Node operator += (const Lazy& x) { return *this = Node(val + x, lazy + x); }
    Node operator + (const Node& x) const { return Node(x.val + val, Lazy()); }
  };
  
  vector<Node> aint;
  
  int n, L_limit, R_limit;
  
  void init(int _n) {
    n = _n;
    L_limit = 1;
    R_limit = n;
    aint.resize(2 * n + 5, Node(ID_M, ID_L));
    fill(all(aint), Node(ID_M, ID_L));
  }
  
  void init(int L, int R) {
    n = R - L + 1;
    L_limit = L;
    R_limit = R;
    aint.resize(2 * n + 5, Node(ID_M, ID_L));
    fill(all(aint), Node(ID_M, ID_L));
  }
  
  void push(int node, int L, int R) {
    if(aint[node].lazy != ID_L)
    aint[L] += aint[node].lazy;
    aint[R] += aint[node].lazy;
    aint[node].lazy = ID_L;
  }
  
  tii get_sons(int node, int cl, int cr) {
    return {cl + cr >> 1, node + 1, node + ((cl + cr >> 1) - cl + 1) * 2};
  }
  
  template<typename VecType>
  void write(const VecType& v) {
    write<VecType>(v, 1, 1, n);
  }
  
  template<typename VecType>
  void write(const VecType& v, int node, int cl, int cr) {
    if(cl == cr) {
      aint[node].val = v[cl];
      aint[node].lazy = ID_L;
      return;
    }
    
    auto [mid, L, R] = get_sons(node, cl, cr);
    
    write(v, L, cl, mid);
    write(v, R, mid + 1, cr);
    
    aint[node] = aint[L] + aint[R];
    return;
    
  }
  
  void set(int p, Mono val) { set(p, val, 1, L_limit, R_limit); }
  
  void set(int p, Mono val, int node, int cl, int cr) {
    if(cr < p || p < cl) return;
    if(cl == cr) { aint[node].val = val; return; }
    
    auto [mid, L, R] = get_sons(node, cl, cr);
    
    push(node, L, R);
    
    set(p, val, L, cl, mid);
    set(p, val, R, mid + 1, cr);
    aint[node] = aint[L] + aint[R];
    
    return;
  }
  
  void upd(int l, int r, Lazy x) { upd(l, r, x, 1, L_limit, R_limit); }
  
  void upd(int l, int r, Lazy x, int node, int cl, int cr) {
    if(cr < l || r < cl) return;
    if(l <= cl && cr <= r) {
      aint[node] += x;
      return;
    }
    
    auto [mid, L, R] = get_sons(node, cl, cr);
    
    push(node, L, R);
    
    upd(l, r, x, L, cl, mid);
    upd(l, r, x, R, mid + 1, cr);
    aint[node] = aint[L] + aint[R];
    
    return;
  }
  
  Mono query(int l, int r) { return query(l, r, 1, L_limit, R_limit); }
  
  Mono query(int l, int r, int node, int cl, int cr) {
    if(cr < l || r < cl) return ID_M;
    if(l <= cl && cr <= r) return aint[node].val;
    
    auto [mid, L, R] = get_sons(node, cl, cr);
    
    push(node, L, R);
    
    return query(l, r, L, cl, mid) + query(l, r, R, mid + 1, cr);
  }
  
  template<class CB>
  int find_right(CB&& cb) { return find_right(cb, 1, L_limit, R_limit); }
  
  template<class CB>
  int find_right(CB&& cb, int node, int cl, int cr) {
    if(!cb(aint[node].val, cl, cr)) return cr + 1;
    if(cl == cr) return cl;
    
    auto [mid, L, R] = get_sons(node, cl, cr);
    
    push(node, L, R);
    
    int tmp_rez = find_right(cb, L, cl, mid);
    if(tmp_rez == mid + 1) return find_right(cb, R, mid + 1, cr);
    return tmp_rez;
  }
  
  template<class CB>
  int find_left(CB&& cb) { return find_right(cb, 1, L_limit, R_limit); }  
  
  template<class CB>
  int find_left(CB&& cb, int node, int cl, int cr) {
    if(!cb(aint[node].val, cl, cr)) return cl - 1;
    if(cl == cr) return cl;
    
    auto [mid, L, R] = get_sons(node, cl, cr);
    
    push(node, L, R);
    
    int tmp_rez = find_right(cb, R, mid + 1, cr);
    if(tmp_rez == mid) return find_right(cb, L, cl, mid);
    return tmp_rez;
  }
  
  void print(int node, int cl, int cr) {
    if(cl == cr) {
      fprintf(stderr, "(%d, %d) ", aint[node].val.simple, aint[node].val.active);
      return;
    }
    
    auto [mid, L, R] = get_sons(node, cl, cr);
    
    push(node, L, R);
    
    print(L, cl, mid);
    print(R, mid + 1, cr);
    return;
  }
  
};

struct EMPT {
  EMPT operator +(const EMPT& x) const {return EMPT(); }
  bool operator != (const EMPT& x) const { return 0; }
};

struct Node {
  ll simple;
  ll active;
  
  Node(): simple(0), active(0) {;}
  Node(ll a, ll b): simple(a), active(b) {;}
  
  Node operator +(const Node& x) const { return Node(simple + x.simple, active + x.active); }
  Node operator +(const EMPT& x) const { return *this; }
};

const int nmax = 1e6 + 5;

ll A[nmax], ALimit[nmax], AScore[nmax];
ll B[nmax], BLimit[nmax], BScore[nmax];

vector<pii> eventscol[nmax];

//ll dp[nmax][nmax];

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, m;
  cin >> n >> m;
  
  AINT<Node,EMPT> aint;
  aint.init(1, n); // stocam derivata s_i - s_i-1
  
  for(int i = 1; i <= n; i++)
    cin >> A[i] >> ALimit[i] >> AScore[i];
  
  for(int i = 1; i <= m; i++)
    cin >> B[i] >> BLimit[i] >> BScore[i];
  
  for(int i = 1; i <= n; i++) A[i] += A[i - 1];
  for(int i = 1; i <= m; i++) B[i] += B[i - 1];
  
  //for(int i = 1; i <= n; i++) cerr << A[i] << ' '; cerr << '\n';
  //for(int i = 1; i <= m; i++) cerr << B[i] << ' '; cerr << '\n';
  
  
  ll _0 = 0;
  
  auto pushLineMod = [&](int ptr, int C) {
    auto R = aint.query(ptr, ptr);
    R.active += C;
    aint.set(ptr, R);
  };
  
  auto pushColMod = [&](int ptr, int C) {
    auto R = aint.query(ptr, ptr);
    R.simple += C;
    aint.set(ptr, R);
  };
  
  for(int i = 1; i <= n; i++) _0 += AScore[i] * (AScore[i] < 0);
  for(int i = 1; i <= m; i++) _0 += BScore[i] * (BScore[i] < 0);
  
  for(int i = 1; i <= n; i++) {
    if(ALimit[i] < A[i] || AScore[i] == 0) continue;
    int u = distance(B, upper_bound(B, B + m + 1, ALimit[i] - A[i])) - 1;
    
    if(AScore[i] < 0) {
      //cerr << i << ", " << AScore[i] << ": " << u + 1 << '\n';
      eventscol[u + 1].emplace_back(i, -AScore[i]);
    }
    else {
      //cerr << i << ", " << AScore[i] << ": " << 0 << ' ' << u + 1 << '\n';
      eventscol[0].emplace_back(i, AScore[i]);
      eventscol[u + 1].emplace_back(i, -AScore[i]);
    }
  }
  
  //_0 = 0;
  
  //ll inutil = 0;
  
  //{
      //ll negC = 0;
  
      //for(int i = 1; i <= n; i++)
        //negC += (AScore[i] < 0) * AScore[i];
      //for(int i = 1; i <= m; i++)
        //negC += (BScore[i] < 0) * BScore[i];
      
      //for(int i = 0; i <= n; i++) {
        //for(int j = 0; j <= m; j++) {
          //if(AScore[i + 1] > 0) {
            //if(A[i + 1] + B[j] <= ALimit[i + 1])
              //dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + AScore[i + 1]);
            //else
              //dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
          //}
          //else {
            //if(A[i + 1] + B[j] > ALimit[i + 1])
              //dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - AScore[i + 1]);
            //else
              //dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
          //}
          
          //if(BScore[j + 1] > 0) {
            //if(A[i] + B[j + 1] <= BLimit[j + 1])
              //dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + BScore[j + 1]);
            //else
              //dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]);
          //}
          //else {
            //if(A[i] + B[j + 1] > BLimit[j + 1])
              //dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] - BScore[j + 1]);
            //else
              //dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]);
          //}
        //}
      //}
      
      //cerr << negC << '\n';
      
      //for(int j = 0; j <= m; j++) {
        //for(int i = 1; i <= n; i++)
          //cout << dp[i][j] << ' ';
        //cout << '\t';
        //for(int i = 1; i <= n; i++)
          //cout << dp[i][j] - dp[i - 1][j] << ' ';
        //cout << '\n';
      //}
  //}
  
  //cerr << _0 << '\n';
  
  for(int i = 0; i <= m; i++) {
    
    sort(all(eventscol[i]), [&](auto a, auto b) { return a.second < b.second; });
    
    for(auto [ptr, C] : eventscol[i]) {
      if(C > 0) {
        
        int cpy = C;
        
        auto finder = [&](Node val, int cl, int cr) -> bool {
          if(cr <= ptr) return 0;
          if(val.simple > 0) return 1;
          return 0;
        };
        
        while(1) {
          int nv_ptr = aint.find_right(finder);
          if(nv_ptr == n + 1) break;
          
          auto R = aint.query(nv_ptr, nv_ptr);
          int mn = min(C,  R.simple);
          C -= mn;
          R.simple -= mn;
          aint.set(nv_ptr, R);
          
          if(C == 0) break;
          ptr = nv_ptr;
        }
        
        pushLineMod(ptr, cpy);
      }
      else
        pushLineMod(ptr, C),
        pushColMod(ptr, -C);
    }
    
    if(i == 0 || BScore[i] == 0 || BLimit[i] < B[i]) {
      _0 -= (BScore[i] < 0) * BScore[i];
    //cerr << i << '\n';
      //cerr << _0 << ' ';
    //aint.print(1, 1, n);
    //cerr << "\n---\n";
      continue;
    }
    
    int u = distance(A, upper_bound(A, A + n + 1, BLimit[i] - B[i])) - 1;
    
    //cerr << B[i] << ' ' << BLimit[i] << '\n';
    //cerr << i << ": " << u << ", " << BScore[i] << '\n';
    //cerr << A[u] << ' ' << A[u + 1] << ' ' << BLimit[i] - B[i] << '\n';
     
    _0 += BScore[i] * (BScore[i] > 0);
    
    //inutil += (BScore[i] > 0) * BScore[i];
      
    if(u == n) {
    //cerr << i << '\n';
      //cerr << _0 << ' ';
    //aint.print(1, 1, n);
    //cerr << "\n---\n";
      continue;
    }
    
    if(BScore[i] < 0) {
      pushColMod(u + 1, -BScore[i]);
    }
    else {
      auto finder = [&](Node val, int cl, int cr) -> bool {
        if(cr <= u) return 0;
        if(val.simple > 0) return 1;
        return 0;
      };
      
      while(1) {
        int nv_u = aint.find_right(finder);
        //cerr << nv_u << '\n';
        if(nv_u == n + 1) break;
        
        auto R = aint.query(nv_u, nv_u);
        int mn = min(BScore[i], R.simple);
        BScore[i] -= mn;
        R.simple -= mn;
        aint.set(nv_u, R);
        
        if(BScore[i] == 0) break;
        u = nv_u;
      }
    }
    
  }
  
  auto R = aint.query(1, n);
  
  
  cout << _0 + R.simple + R.active << '\n';

  
}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/

Compilation message (stderr)

dishes.cpp: In instantiation of 'tii AINT<Mono, Lazy>::get_sons(ll, ll, ll) [with Mono = Node; Lazy = EMPT; tii = std::tuple<long long int, long long int, long long int>; ll = long long int]':
dishes.cpp:125:24:   required from 'Mono AINT<Mono, Lazy>::query(ll, ll, ll, ll, ll) [with Mono = Node; Lazy = EMPT; ll = long long int]'
dishes.cpp:119:42:   required from 'Mono AINT<Mono, Lazy>::query(ll, ll) [with Mono = Node; Lazy = EMPT; ll = long long int]'
dishes.cpp:232:33:   required from here
dishes.cpp:56:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     return {cl + cr >> 1, node + 1, node + ((cl + cr >> 1) - cl + 1) * 2};
      |             ~~~^~~~
dishes.cpp:56:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     return {cl + cr >> 1, node + 1, node + ((cl + cr >> 1) - cl + 1) * 2};
      |                                              ~~~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9