Submission #439465

#	Time	Username	Problem	Language	Result	Execution time	Memory
439465		fcmalkcin	Food Court (JOI21_foodcourt)	C++17	100 / 100	673 ms	54276 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn=3e5+10;
const ll mod =998244353 ;
const ll base=3e18;
vector<pair<pll,ll>> adj[maxn];
vector<pll> p[maxn];

struct tk
{
    ll val,c;
    ll mn;
    ll ps;
};
tk st[4*maxn];
tk mer(tk a,tk b)
{
    if (a.c==-1)
        return b;
    if (b.c==-1)
        return a;
    tk c;
    c.val=a.val+b.val;
    c.mn=min(a.mn,a.val+b.mn);
    c.ps=a.ps+b.ps;
    c.c=base;
    //  cout <<c.val<<" "<<c.mn<<" "<<c.ps<<" "<<c.c<<"chkmer"<<endl;
    return c;
}
void build(ll id,ll left,ll right)
{
    st[id].val=0;
    st[id].c=0;
    st[id].mn=0;
    st[id].ps=0;
    if (left==right)
        return ;
    ll mid=(left+right)/2;
    build(id*2,left,mid);
    build(id*2+1,mid+1,right);
}
void update(ll id,ll left,ll right,ll x,ll val,ll c)
{
    if (x>right||x<left)
        return ;
    if (left==right)
    {
        st[id].val=val;
        st[id].mn=min(0ll,st[id].val);
        st[id].ps=max(0ll,st[id].val);
        st[id].c=c;
        return ;
    }
    ll mid=(left+right)/2;
    update(id*2,left,mid,x,val,c);
    update(id*2+1,mid+1,right,x,val,c);
    st[id]=mer(st[id*2],st[id*2+1]);
}
tk get(ll id,ll left,ll right,ll x,ll y)
{
    tk p;
    p.c=-1;
    if (x>right||y<left)
        return p;
    if (x<=left&&y>=right)
    {
        //cout <<st[id].c<<" "<<st[id].mn<<" "<<st[id].ps<<" "<<st[id].val<<endl;
        return st[id];
    }
    ll mid=(left+right)/2;
    return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
}
ll walk(ll id,ll left,ll right,ll val)
{
    if (left==right)
    {
        return st[id].c;
    }
    ll mid=(left+right)/2;
    if (val<st[id*2].ps)
    {
        return walk(id*2,left,mid,val);
    }
    return walk(id*2+1,mid+1,right,val-st[id*2].ps);
}
ll ans[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    memset(ans,-1,sizeof(ans));
    ll n, m, q;
    cin>> n>> m>> q;
    for (int i=1; i<=q; i++)
    {
        ll t;
        cin>> t;
        if (t==1)
        {
            ll l, r, c, k;
            cin>> l>> r>> c>> k;
            adj[l].pb(make_pair(make_pair(i,c),k));
            adj[r+1].pb(make_pair(make_pair(i,0),0));
        }
        else if (t==2)
        {
            ll l, r, c, k;
            cin>> l>> r>> k;
            c=0;
            adj[l].pb(make_pair(make_pair(i,c),-k));
            adj[r+1].pb(make_pair(make_pair(i,c),0));
        }
        else
        {
            ll a, b;
            cin>> a>> b;
            p[a].pb(make_pair(i,b));
        }
    }
    build(1,1,q+1);
    update(1,1,q+1,1,-base,-1);

    for (int i=1; i<=n; i++)
    {
        for (auto p:adj[i])
        {
            update(1,1,q+1,p.ff.ff+1,p.ss,p.ff.ss);
        }

        for (auto to:p[i])
        {
            ll val=to.ss;
            ll pos=to.ff+1;
            tk h=get(1,1,q+1,1,pos);
            ll nw=h.val-h.mn;
            ans[pos-1]=0;
            if (nw>=val)
            {
                ll sl=nw-val+1;
                ll sum=get(1,1,q+1,1,pos).ps;
                ans[pos-1]=walk(1,1,q+1,sum-sl);
            }
        }
    }
    for (int i=1; i<=q; i++)
    {
        if (ans[i]==-1)
            continue;
        cout <<ans[i]<<endl;
    }
    /*3 5 5
    1 2 3 5 2
    1 1 2 2 4
    2 1 3 3
    1 2 3 4 2
    3 3 2*/

}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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