제출 #1255576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255576		LucaLucaM	푸드 코트 (JOI21_foodcourt)	C++20	68 / 100	1095 ms	14324 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;
  ll aux;
};

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);
            if (i < h) add[i] += a;
        }
        void push(int i) {
            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 (ib <= a || b <= ia) return -INF;
            if (a <= ia && ib <= b) return cap[i];
            
            push(i);
            int im = (ia + ib) >> 1;
            return max(recMax(a, b, 2*i, ia, im), recMax(a, b, 2*i+1, im, ib));
        }
        void init(int n) {
            h = 1;
            while(h < n) h <<= 1;
            add.assign(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, (int) Q.size(), (int) U.size() - 1, 0, aib.query(A)});
    }
  }
  
  Beats DS1;
  
  for (int jump = (1 << 17); jump > 0; jump >>= 1) {
    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);
    });
  
    DS1.init(n);
    aib.init(n);
    int ptr = 0;
    for (auto &[A, B, index, indexupdates, answer, aux] : Q) {
      int newAnswer = std::min(answer + jump, indexupdates);
      while (ptr < newAnswer) {
        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);
        }
      }
      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