제출 #1256474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256474		LucaLucaM	푸드 코트 (JOI21_foodcourt)	C++20	89 / 100	1092 ms	23708 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 nuBeats { 
        const ll INF = 4e18;
        vector<ll> add, lower;
        int h = 1;
 
        void apply(int i, ll a, ll b) {
          lower[i] = std::max(lower[i] + a, b);
          add[i] += a;
        }
        void push(int i) {
            if (i <= h) {
              apply(2*i, add[i], lower[i]);
              apply(2*i+1, add[i], lower[i]);
            }
            add[i] = 0;
            lower[i] = 0;
        }
 
        void update(int node, int tl, int tr, int l, int r, ll v) {
          if (l <= tl && tr <= r) {
            apply(node, v, 0);
          } else {
            push(node);
            int mid = (tl + tr) / 2;
            if (l <= mid) {
              update(2 * node, tl, mid, l, r, v);
            } 
            if (mid < r) {
              update(2 * node + 1, mid + 1, tr, l, r, v);
            }
          }
        }
        ll query(int node, int tl, int tr, int p) {
          if (tl == tr) {
            return lower[node];
          }
          push(node);
          int mid = (tl + tr) / 2;
          if (p <= mid) {
            return query(2 * node, tl, mid, p);
          } else {
            return query(2 * node + 1, mid + 1, tr, p);
          }
        }
        void init(int n) {
            h = 1;
            while(h <= n) h <<= 1;
            add.assign(2 * h + 1, 0);
            lower.assign(2 * h + 1, 0);
          }
        void reset() {
            add.assign(2 * h + 1, 0);
            lower.assign(2 * h + 1, 0);
        }
 
        void updateAdd(int a, int b, ll v) {update(1, 1, h, a, b, v); apply(1, 0, 0); }
        ll query(int i) {return query(1, 1, h, i);}
};

struct Fenwick {
  std::vector<ll> aib;
  int n;
  
  void init(int _n) {
    n = _n + 1;
    aib.assign(n, 0);
  }
  void reset() {
    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);

  nuBeats DS1;
  DS1.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});
      if (m == 1) {
        DS1.updateAdd(l, r, +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});
      if (m == 1) {
        DS1.updateAdd(l, r, -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});
      if (m == 1) {
        std::cout << (DS1.query(A) >= B) << '\n';
      }
    }
  }
  if (m == 1) {
    return 0;
  }
  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.reset();
    aib.reset();

    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]) {
        if (DS1.query(Q[i].A) + aib.query(Q[i].A) < Q[i].B) {
          Q[i].answer = std::min(Q[i].answer + jump, Q[i].indexupdates);
        }
      }
      ids[ptr].clear();
    }
  }
  
  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: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 0 / 11