Submission #957946

#	Time	Username	Problem	Language	Result	Execution time	Memory
957946		12345678	Food Court (JOI21_foodcourt)	C++17	2 / 100	372 ms	59132 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=250005;

ll n, m, q, t, l, r, c[nx], k, a, b, res[nx];

struct query
{
    ll t, typ, k;
    query(ll t, ll typ, ll k): t(t), typ(typ), k(k){}
};
vector<query> v[nx], qrs[nx];

struct fenwick
{
    int d[nx];
    void add(int i, int vl) {while (i<nx) d[i]+=vl, i+=(i&-i);}
    ll query(int i)
    {
        ll res=0;
        while (i>0) res+=d[i], i-=(i&-i);
        return res;
    }
    ll query(int l, int r)
    {
        if (r<l) return 0;
        return query(r)-query(l-1);
    }
} up, dn;

struct segtree
{
    struct node
    {
        ll mn, mnidx, lz;
        node(): mn(0), mnidx(0), lz(0) {}
        node(ll mn, ll mnidx, ll lz): mn(mn), mnidx(mnidx), lz(lz) {}
        friend node operator+ (const node &a, const node &b)
        {
            if (b.mn<a.mn) return node(b.mn, b.mnidx, 0);
            return node(a.mn, a.mnidx, 0);
        }
    } d[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i].mn+=d[i].lz;
        if (l==r) return d[i].lz=0, void();
        d[2*i].lz+=d[i].lz;
        d[2*i+1].lz+=d[i].lz;
        d[i].lz=0;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]=node(0, l, 0), void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=d[2*i]+d[2*i+1];
    }
    void update(int l, int r, int i, int ql, int qr, ll vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return d[i].lz+=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    node query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return node(1e18, 0, 0);
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
    void show(int l, int r, int i)
    {
        pushlz(l, r, i);
        if (l==r) return cout<<d[i].mn<<' ', void();
        int md=(l+r)/2;
        show(l, md, 2*i);
        show(md+1, r, 2*i+1);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<=q; i++)
    {
        res[i]=-1;
        cin>>t;
        if (t==1)
        {
            cin>>l>>r>>c[i]>>k;
            v[l].push_back(query(i, 1, k));
            v[r+1].push_back(query(i, 1, -k));
        }
        if (t==2)
        {
            cin>>l>>r>>k;
            v[l].push_back(query(i, 2, k));
            v[r+1].push_back(query(i, 2, -k));
        }
        if (t==3) 
        {
            cin>>a>>b;
            qrs[a].push_back(query(i, 0, b));
        }
    }
    s.build(0, q, 1);
    for (int i=1; i<=n; i++)
    {
        for (auto x:v[i])
        {
            if (x.typ==1) s.update(0, q, 1, x.t, q, x.k), up.add(x.t, x.k);
            else s.update(0, q, 1, x.t, q, -x.k), dn.add(x.t, x.k);
        }
        /*
        cout<<"debug "<<i<<':';
        s.show(0, q, 1);
        cout<<'\n';
        cout<<"mnidx "<<s.d[1].mn<<' '<<s.d[1].mnidx<<'\n';
        */
        for (auto x:qrs[i])
        {
            ll idx=s.query(0, q, 1, 0, x.t).mnidx, cnt=dn.query(idx+1, x.t)+x.k;
            //cout<<"cnt "<<cnt<<' '<<"idx "<<idx<<'\n';
            if (up.query(idx+1, x.t)<cnt) res[x.t]=0;
            else
            {
                l=idx+1, r=x.t;
                while (l<r)
                {
                    int md=(l+r)/2;
                    //cout<<l<<' '<<r<<' '<<md<<' '<<up.query(idx+1, md)<<'\n';
                    if (up.query(idx+1, md)>=cnt) r=md;
                    else l=md+1;
                }
                res[x.t]=c[l];
            }
        }
    }
    for (int i=1; i<=q; i++) if (res[i]!=-1) cout<<res[i]<<'\n';
}

/*
183326 218318 22
1 106761 160918 151683 574906362
3 68709 1
1 29240 156379 22166 957318472
1 14054 181502 82845 97183925
2 112033 122908 587808357
2 57819 160939 215041262
3 36674 524274467
1 35854 69866 32334 322730299
1 1384 7230 115069 454256926
1 44192 158235 8750 84192710
3 54457 1077490708
2 10592 110384 979714505
2 44594 79244 311724477
3 160965 97183926
1 88748 101697 39148 373927458
3 41166 58039001
1 91501 137591 205480 958877326
2 77775 169655 135756956
1 12497 57047 60918 15666764
1 47839 51716 144688 732270998
3 114514 774994894
3 48645 169986425
*/

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