제출 #493409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493409		blue	푸드 코트 (JOI21_foodcourt)	C++17	100 / 100	859 ms	83632 KiB

foodcourt

#include <iostream>
#include <vector>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

const int mx = 250'000;
const ll INF = 1'000'000'000'000'000'000LL;

vi L(1+mx), R(1+mx), C(1+mx), A(1+mx);
vll K(1+mx), B(1+mx);
vi T(1+mx);

vi st[1+mx], en[1+mx], qr[1+mx];

vi ans(1+mx, 0);



struct segtree
{
    int l;
    int r;

    pair<ll, int> mn;
    ll lp = 0;

    segtree* left = NULL;
    segtree* right = NULL;


    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        mn = {0, l};
        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void add(int L, int R, ll V)
    {
        if(r < L || R < l) return;
        else if(L <= l && r <= R)
        {
            lp += V;
            mn.first += V;
        }
        else
        {
            left->add(L, R, V);
            right->add(L, R, V);
            mn = min(left->mn, right->mn);
            mn.first += lp;
        }
    }

    pair<ll, int> rangemin(int L, int R)
    {
        if(R < l || r < L) return {INF, -1};
        else if(L <= l && r <= R) return mn;
        else
        {
            auto res = min(left->rangemin(L, R), right->rangemin(L, R));
            res.first += lp;
            return res;
        }
    }
};

struct BIT
{
    int Z;
    vll arr;

    BIT()
    {
        ;
    }

    BIT(int z)
    {
        Z = z;
        arr = vll(1+z, 0);
    }

    void add(int i, ll v)
    {
        for(int j = i; j <= Z; j += j&-j)
            arr[j] += v;
    }

    ll prefsum(int i)
    {
        ll ans = 0;
        for(int j = i; j >= 1; j -= j&-j)
            ans += arr[j];
        return ans;
    }
};



int main()
{
    int N, M, Q;
    cin >> N >> M >> Q;

    for(int j = 1; j <= Q; j++)
    {
        cin >> T[j];
        if(T[j] == 1) cin >> L[j] >> R[j] >> C[j] >> K[j];
        else if(T[j] == 2)
        {
            cin >> L[j] >> R[j] >> K[j];
            K[j] *= -1;
        }
        else cin >> A[j] >> B[j];

        if(T[j] <= 2)
        {
            st[L[j]].push_back(j);
            en[R[j]].push_back(j);
        }
        else qr[A[j]].push_back(j);
    }

    vll S(1+Q, 0);

    vi ans(1+Q, 0);

    segtree ST(0, Q);
    BIT plus_sum(1+Q), minus_sum(1+Q);

    for(int i = 1; i <= N; i++)
    {
        for(int o: st[i])
        {
            S[o] = K[o];
            ST.add(o, Q, +K[o]);
            if(K[o] > 0)
                plus_sum.add(o, +K[o]);
            else
                minus_sum.add(o, -K[o]);
        }

        for(int q: qr[i])
        {
            int p = ST.rangemin(0, q-1).second;

            ll min_sum = minus_sum.prefsum(q) - minus_sum.prefsum(p);

            // cerr << "p = " << p << '\n';
            // cerr << "total loss = " << minus_sum << '\n';

            ll plus_sub = plus_sum.prefsum(p);

            int lo = p+1;
            int hi = q+1;
            while(lo != hi)
            {
                int mid = (lo+hi)/2;
                if(plus_sum.prefsum(mid) - plus_sub >= min_sum + B[q])
                    hi = mid;
                else
                    lo = mid+1;
            }
            if(lo != q+1)
            {
                ans[q] = C[lo];
            }

            // ll plus_sum = 0;
            // for(int j = p+1; j <= q; j++)
            // {
            //     if(S[j] > 0)
            //         plus_sum += S[j];
            //
            //     if(plus_sum >= min_sum + B[q])
            //     {
            //         ans[q] = C[j];
            //         break;
            //     }
            // }
        }

        for(int o: en[i])
        {
            S[o] = 0;
            ST.add(o, Q, -K[o]);
            if(K[o] > 0)
                plus_sum.add(o, -K[o]);
            else
                minus_sum.add(o, +K[o]);
        }
    }



    for(int q = 1; q <= Q; q++)
        if(T[q] == 3)
            cout << ans[q] << '\n';
    // cout << '\n';
}

• 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: 11 / 11