Submission #439458

#	Time	Username	Problem	Language	Result	Execution time	Memory
439458		fcmalkcin	Food Court (JOI21_foodcourt)	C++17	68 / 100	1095 ms	58692 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,mx;
    ll ps;
    ll chk;
};
tk st[4*maxn];
tk mer(tk a,tk b)
{
    if (a.chk==-1) return b;
    if (b.chk==-1) return a;
    tk c;
    c.val=a.val+b.val;
    c.chk=a.chk;
    c.mn=min(a.mn,a.val+b.mn);
    c.mx=max(a.mx,a.val+b.mx);
    c.ps=a.ps+b.ps;
    c.c=-1;
    return c;
}
void build(ll id,ll left,ll right)
{
    st[id].val=0;
    st[id].chk=-1;
    st[id].c=-1;
    st[id].mn=0;
    st[id].mx=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);
    st[id]=mer(st[id*2],st[id*2+1]);
}
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].mx=max(0ll,st[id].val);
        st[id].mn=min(0ll,st[id].val);
        st[id].chk=(val>=0);
        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.chk=-1;
    if (x>right||y<left) return p;
    if (x<=left&&y>=right)
    {
        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 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,c),0));
        }
        else if (t==2)
        {
             ll l, r, c, k;
            cin>> l>> r>> k;
            c=-1;
            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 (i==3)   cout <<nw<<" "<<val<<" "<<i<<endl;
               if (nw>=val)
               {
                   ll sl=nw-val+1;
             //    if (i==3) cout <<sl<<" "<<pos<<endl;
                   ll l=1, h=pos;
                   while (l<=h)
                   {
                       ll mid=(l+h)/2;
                       tk g=get(1,1,q+1,mid,pos);
                       if (g.ps>=sl) l=mid+1;
                       else h=mid-1;
                   }
                   tk g=get(1,1,q+1,h,h);
                  /* if (i==3)
                   {
                   cout <<h<<" wtf"<<endl;
                   cout <<g.c<<" "<<g.mn<<" "<<g.mx<<" "<<g.ps<<" "<<g.val<<endl;
                   }*/
                   ans[pos-1]=g.c;
               }
           }
    }
    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:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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