Submission #1255564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255564		LucaLucaM	Food Court (JOI21_foodcourt)	C++20	27 / 100	1097 ms	48668 KiB

foodcourt

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

using namespace std;

#define int ll

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

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

struct Query {
  int A, B, index, indexupdates, answer, aux;
};
const ll INF = (1LL<<60);

struct Beats { // asta e scris de gpt (sper ca merge)
  
    struct Node {
        ll sum;
        ll mn, smin;    // minimum and second-minimum
        int mcnt;       // count of minimum
        ll add;         // lazy add
        Node(): sum(0), mn(INF), smin(INF), mcnt(0), add(0) {}
        void set_val(ll v) {
            sum = v;
            mn = v;
            smin = INF;
            mcnt = 1;
            add = 0;
        }
    };
    int n;
    vector<Node> st;
    Beats(): n(0) {}
    Beats(int _n, bool init_zero = true) { init(_n, init_zero); }

    void init(int _n, bool init_zero = true) {
        n = _n;
        st.assign(4*max(1LL,n)+5, Node());
        if (n && init_zero) build_zeros(1,0,n-1);
    }

    void build_zeros(int p, int l, int r) {
        if (l==r) { st[p].set_val(0); return; }
        int m=(l+r)>>1;
        build_zeros(p<<1,l,m);
        build_zeros(p<<1|1,m+1,r);
        pull(p);
    }

    void build(const vector<ll>& a) {
        n = (int)a.size();
        st.assign(4*max(1LL,n)+5, Node());
        build_rec(1, 0, n-1, a);
    }

    void build_rec(int p, int l, int r, const vector<ll>& a) {
        if (l == r) { st[p].set_val(a[l]); return; }
        int m = (l+r)>>1;
        build_rec(p<<1, l, m, a);
        build_rec(p<<1|1, m+1, r, a);
        pull(p);
    }

    void pull(int p) {
        const Node &L = st[p<<1], &R = st[p<<1|1];
        Node &X = st[p];
        X.sum = L.sum + R.sum;
        if (L.mn < R.mn) {
            X.mn = L.mn;
            X.mcnt = L.mcnt;
            X.smin = min(L.smin, R.mn);
        } else if (L.mn > R.mn) {
            X.mn = R.mn;
            X.mcnt = R.mcnt;
            X.smin = min(L.mn, R.smin);
        } else {
            X.mn = L.mn;
            X.mcnt = L.mcnt + R.mcnt;
            X.smin = min(L.smin, R.smin);
        }
    }

    void apply_add(int p, ll v, int len) {
        if (len <= 0) return;
        st[p].sum += v * (ll)len;
        st[p].mn += v;
        if (st[p].smin < INF/2) st[p].smin += v;
        st[p].add += v;
    }

    void apply_chmax_node(int p, ll x) {
        // precondition: x > st[p].mn and st[p].smin > x
        st[p].sum += (x - st[p].mn) * (ll)st[p].mcnt;
        st[p].mn = x;
        // smin remains > x by precondition
    }

    void push(int p, int l, int r) {
        if (l == r) { st[p].add = 0; return; }
        int m = (l+r)>>1, L = p<<1, R = p<<1|1;
        int lenL = m - l + 1, lenR = r - m;

        if (st[p].add != 0) {
            ll v = st[p].add;
            apply_add(L, v, lenL);
            apply_add(R, v, lenR);
            st[p].add = 0;
        }

        if (st[L].mn < st[p].mn) {
            if (st[L].smin > st[p].mn) apply_chmax_node(L, st[p].mn);
        }
        if (st[R].mn < st[p].mn) {
            if (st[R].smin > st[p].mn) apply_chmax_node(R, st[p].mn);
        }
    }

    // range add [L,R] (0-based)
    void range_add(int L, int R, ll v) { if (L>R) return; range_add_rec(1,0,n-1,L,R,v); }
    void range_add_rec(int p, int l, int r, int L, int R, ll v) {
        if (R < l || r < L) return;
        if (L <= l && r <= R) {
            apply_add(p, v, r-l+1);
            return;
        }
        push(p, l, r);
        int m = (l+r)>>1;
        range_add_rec(p<<1, l, m, L, R, v);
        range_add_rec(p<<1|1, m+1, r, L, R, v);
        pull(p);
    }

    // range chmax: a[i] = max(a[i], x) on [L,R] (0-based)
    void range_chmax(int L, int R, ll x) { if (L>R) return; range_chmax_rec(1,0,n-1,L,R,x); }
    void range_chmax_rec(int p, int l, int r, int L, int R, ll x) {
        if (R < l || r < L || st[p].mn >= x) return;
        if (L <= l && r <= R && st[p].smin > x) {
            apply_chmax_node(p, x);
            return;
        }
        push(p, l, r);
        int m = (l+r)>>1;
        range_chmax_rec(p<<1, l, m, L, R, x);
        range_chmax_rec(p<<1|1, m+1, r, L, R, x);
        pull(p);
    }

    // range sum [L,R] (0-based)
    ll range_sum(int L, int R) { if (L>R) return 0; return range_sum_rec(1,0,n-1,L,R); }
    ll range_sum_rec(int p, int l, int r, int L, int R) {
        if (R < l || r < L) return 0;
        if (L <= l && r <= R) return st[p].sum;
        push(p, l, r);
        int m = (l+r)>>1;
        return range_sum_rec(p<<1, l, m, L, R) + range_sum_rec(p<<1|1, m+1, r, L, R);
    }

    ll point_get(int idx) { return range_sum(idx, idx); }

    void updateAdd(int l, int r, int x) { 
      range_add(l - 1, r - 1, x);
    }
    void updateMax0() {
      range_chmax(0, n - 1, 0);
    }
    ll query(ll p) {
      return point_get(p - 1);
    }
};

struct Fenwick {
  std::vector<ll> aib;
  int n;
  
  void init(int _n) {
    n = _n + 1;
    aib.assign(n + 3, 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, 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 << 18); 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 + 2);
    aib.init(n + 1);
    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) {
          DS1.updateMax0();
          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: 0 / 15
• Subtask 6: 13 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11