Submission #541710

#	Time	Username	Problem	Language	Result	Execution time	Memory
541710		Fysty	Food Court (JOI21_foodcourt)	C++17	100 / 100	415 ms	48272 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
const ll INF=3e18;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
//#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end());uni(c)

const int N=250005;


struct BIT
{
    ll sz,a[N];
    void upd(int x,ll val){for(;x<=sz;x+=x&-x) a[x]+=val;}
    ll qry(int x)
    {
        ll ret=0;
        for(;x;x-=x&-x) ret+=a[x];
        return ret;
    }
} bit;
struct SegTree1
{
    ll tag[N<<2],mn[N<<2];
    void givetag(ll x,ll y,int id)
    {
        mn[id]=min(mn[id],tag[id]+y);
        tag[id]+=x;
    }
    void tagdown(int id)
    {
        givetag(tag[id],mn[id],id<<1);
        givetag(tag[id],mn[id],id<<1|1);
        tag[id]=mn[id]=0;
    }
    void upd(int l,int r,int ql,int qr,ll x,int id)
    {
        if(ql<=l&&r<=qr) givetag(x,x,id);
        else
        {
            tagdown(id);
            int mid=l+r>>1;
            if(qr<=mid) upd(l,mid,ql,qr,x,id<<1);
            else if(ql>mid) upd(mid+1,r,ql,qr,x,id<<1|1);
            else
            {
                upd(l,mid,ql,mid,x,id<<1);
                upd(mid+1,r,mid+1,qr,x,id<<1|1);
            }
        }
    }
    ll qry(int l,int r,int x,int id)
    {
        if(l==r) return tag[id]-mn[id];
        else
        {
            tagdown(id);
            int mid=l+r>>1;
            if(x<=mid) return qry(l,mid,x,id<<1);
            else return qry(mid+1,r,x,id<<1|1);
        }
    }
} seg1;

struct SegTree2
{
    ll st[N<<2];
    void upd(int l,int r,int x,ll val,int id)
    {
        if(l==r) st[id]+=val;
        else
        {
            int mid=l+r>>1;
            if(x<=mid) upd(l,mid,x,val,id<<1);
            else upd(mid+1,r,x,val,id<<1|1);
            st[id]=st[id<<1]+st[id<<1|1];
        }
    }
    ll qry(int l,int r,ll x,int id)
    {
        if(l==r) return l;
        else
        {
            int mid=l+r>>1;
            if(st[id<<1]>=x) return qry(l,mid,x,id<<1);
            else return qry(mid+1,r,x-st[id<<1],id<<1|1);
        }
    }
} seg2;

ll ans[N],r[N],color[N];//ans,modified qry
vector<pll> add[N];//{time,val}
vector<int> id[N];

signed main()
{
    MottoHayaku
    int n,m,q;
    cin>>n>>m>>q;
    bit.sz=n;
    rep1(i,q)
    {
        ll t;
        cin>>t;
        ans[i]=-1;
        if(t==1)
        {
            int l,r,c;
            ll k;
            cin>>l>>r>>c>>k;
            color[i]=c;
            seg1.upd(1,n,l,r,k,1);
            add[l].pb({i,k});
            if(r<n) add[r+1].pb({i,-k});
            bit.upd(l,k);
            bit.upd(r+1,-k);
        }
        else if(t==2)
        {
            int l,r;
            ll k;
            cin>>l>>r>>k;
            seg1.upd(1,n,l,r,-k,1);
        }
        else
        {
            int a;
            ll b;
            cin>>a>>b;
            ll tmp=b-seg1.qry(1,n,a,1);
            if(tmp>0)
            {
                ans[i]=0;
                continue;
            }
            r[i]=bit.qry(a)+tmp;
            id[a].pb(i);
        }
    }
    rep1(i,n)
    {
        for(pll u:add[i]) seg2.upd(1,q,u.F,u.S,1);
        for(ll u:id[i]) ans[u]=color[seg2.qry(1,q,r[u],1)];
    }

    rep1(i,q)
    {
        if(ans[i]!=-1) cout<<ans[i]<<"\n";
    }
}

Compilation message (stderr)

foodcourt.cpp: In member function 'void SegTree1::upd(int, int, int, int, ll, int)':
foodcourt.cpp:54:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |             int mid=l+r>>1;
      |                     ~^~
foodcourt.cpp: In member function 'll SegTree1::qry(int, int, int, int)':
foodcourt.cpp:70:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |             int mid=l+r>>1;
      |                     ~^~
foodcourt.cpp: In member function 'void SegTree2::upd(int, int, int, ll, int)':
foodcourt.cpp:85:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |             int mid=l+r>>1;
      |                     ~^~
foodcourt.cpp: In member function 'll SegTree2::qry(int, int, ll, int)':
foodcourt.cpp:96:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |             int mid=l+r>>1;
      |                     ~^~

• 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