Submission #1255587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255587		LucaLucaM	Food Court (JOI21_foodcourt)	C++20	68 / 100	1096 ms	23804 KiB

foodcourt

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

struct Update {
  int type, l, r, c, k;
};  

struct Query {
  int A;
  ll B;
  int index, indexupdates, answer;
};

struct Beats { // asta e straight up copiat 
        const ll INF = 4 * (ll)1e18;
        vector<ll> add, cap;
        int h = 1;
 
        void apply(int i, ll a, ll c) {
            cap[i] = min(cap[i] + a, c);
            add[i] += a;
        }
        void push(int i) {
            if (i < h) {
              apply(2*i, add[i], cap[i]);
              apply(2*i+1, add[i], cap[i]);
            }
            add[i] = 0;
            cap[i] = INF;
        }
 
        void recAdd(int a, int b, ll v, int i, int ia, int ib) {
            if (a <= ia && ib <= b) apply(i, v, INF);
            else {
                push(i);
                int im = (ia + ib) >> 1;
                if (a < im) {
                  recAdd(a, b, v, 2*i, ia, im);
                }
                if (im < b) {
                  recAdd(a, b, v, 2*i+1, im, ib);
                }
            }
        }
        ll recMax(int a, int b, int i, int ia, int ib) {
            if (a <= ia && ib <= b) return cap[i];
            
            push(i);
            int im = (ia + ib) >> 1;
            if (a < im && im < b) {
              return max(recMax(a, b, 2*i, ia, im), recMax(a, b, 2*i+1, im, ib));
            } else if (a < im) {
              return recMax(a, b, 2 * i, ia, im);
            } else {
              return recMax(a, b, 2 * i + 1, im, ib);
            }
        }
        void init(int n) {
            h = 1;
            while(h < n) h <<= 1;
            add.assign(2*h, 0);
            cap.assign(2*h, 0);
        }
 
        void updateAdd(int a, int b, ll v) {recAdd(a-1, b, -v, 1, 0, h); apply(1, 0, 0); }
        ll query(int i) {return -recMax(i-1, i, 1, 0, h); }
};

struct Fenwick {
  std::vector<ll> aib;
  int n;
  
  void init(int _n) {
    n = _n + 1;
    aib.assign(n, 0);
  }

  void update(int p, int v) {
    for (; p < n; p += p & -p) {
      aib[p] += v;
    }
  }
  ll query(int p) {
    ll ret = 0;
    for (; p > 0; p -= p & -p) {
      ret -= aib[p];
    }
    return ret;
  }
};

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);

  int n, m, q;
  std::cin >> n >> m >> q;

  std::vector<Update> U;
  std::vector<Query> Q;

  U.push_back(Update{});

  Fenwick aib;
  aib.init(n);

  for (int i = 1; i <= q; i++) {
    int type;
    std::cin >> type;
    if (type == 1) {
      int l, r, c, k;
      std::cin >> l >> r >> c >> k;
      U.push_back({type, l, r, c, k});
    } else if (type == 2) {
      int l, r, k;
      std::cin >> l >> r >> k;
      aib.update(l, k);
      aib.update(r + 1, -k);
      U.push_back({type, l, r, 0, -k});
    } else {
      int A;
      ll B;
      std::cin >> A >> B;
      Q.push_back({A, B - aib.query(A), (int) Q.size(), (int) U.size() - 1, 0});
    }
  }
  
  Beats DS1;
  
  std::vector<std::vector<int>> ids((int) U.size());

  for (int jump = (1 << 17); jump > 0; jump >>= 1) {
    for (auto i : Q) {
      ids[std::min(i.answer + jump, i.indexupdates)].push_back(i.index);
    }
    
    DS1.init(n);
    aib.init(n);

    for (int ptr = 1; ptr < (int) U.size(); ptr++) {
      DS1.updateAdd(U[ptr].l, U[ptr].r, U[ptr].k);
      if (U[ptr].type == 2) {
        aib.update(U[ptr].l, U[ptr].k);
        aib.update(U[ptr].r + 1, -U[ptr].k);
      }
      for (int i : ids[ptr]) {
        auto &[A, B, index, indexupdates, answer] = Q[i];
        if (DS1.query(A) + aib.query(A) < B) {
          answer = std::min(answer + jump, indexupdates);
        }
      }
      ids[ptr].clear();
    }
    // std::sort(Q.begin(), Q.end(), [&](Query a, Query b) {
    //   return std::min(a.answer + jump, a.indexupdates) < std::min(b.answer + jump, b.indexupdates);
    // });
  
    // int ptr = 0;
    // for (auto &[A, B, index, indexupdates, answer, aux] : Q) {
    //   int newAnswer = std::min(answer + jump, indexupdates);
    //   while (ptr < newAnswer) {
    //     ptr++;
    //   }
    //   if (DS1.query(A) + aux + aib.query(A) < B) {
    //     answer = newAnswer;
    //   }
    // }
  }
  
  // std::sort(Q.begin(), Q.end(), [](Query a, Query b) {
  //   return a.index < b.index;
  // });
  
  for (auto i : Q) {
    if (i.answer < i.indexupdates) {
      i.answer++;
      std::cout << U[i.answer].c << '\n';
    } else {
      std::cout << "0\n";
    }
  }
  
  return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 0 / 11