Submission #564165

#	Time	Username	Problem	Language	Result	Execution time	Memory
564165		fcmalkcin	Ants and Sugar (JOI22_sugar)	C++17	0 / 100	101 ms	219508 KiB

sugar

#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"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=5e5+10;
const ll mod=1e9+7  ;
const ll base=3e18;

ll t[maxn];
ll x[maxn];
ll a[maxn];
struct tk
{
    ll dp[3][2][2];
    ll la;
    ll la1;
    tk()
    {
        la=0;
        la1=0;
        memset(dp,-0x3f,sizeof(dp));
        dp[1][0][1]=0;
        dp[1][1][1]=0;
        dp[0][0][0]=0;
        dp[0][0][1]=0;
        dp[0][1][0]=0;
    }
};
tk st[4*maxn];
void modify(ll id,ll val,ll val1)
{
    for (int t=0;t<=2;t++)
    {
        st[id].dp[t][0][0]-=val;
        st[id].dp[t][1][1]+=val;
        for (int i=0;i<=1;i++)
        {
            for (int j=0;j<=1;j++)
            {
                if (t==0&&(i||j)) continue;
                st[id].dp[t][i][j]+=(val1*t);
            }
        }
    }
    st[id].la+=val;
    st[id].la1+=val1;
}
void dosth(ll id)
{
    modify(id*2,st[id].la,st[id].la1);
    modify(id*2+1,st[id].la,st[id].la1);
    st[id].la=0;
    st[id].la1=0;
}
tk mer(tk a,tk b)
{
    tk c;
    for (int t=0; t<=2; t++)
    {
        for (int l=0; l<=1; l++)
        {
            for (int r=0; r<=1; r++)
            {
                if (a.dp[t][l][r]==-base)
                    continue;
                ll l1=1-r;
                for (int t1=0; t1<=2; t1++)
                {
                    for (int r1=0; r1<=1; r1++)
                    {
                        c.dp[min(2,t+t1)][l][r1]=max(c.dp[min(2,t+t1)][l][r1],a.dp[t][l][r]+b.dp[t1][l1][r1]);
                    }
                }
            }
        }
    }
    return c;
}
void update(ll id,ll left,ll right,ll x,ll diff)
{
   if (x>right||x<left) return ;
   if (left==right)
   {
        st[id].dp[1][0][1]+=diff;
        st[id].dp[1][1][1]+=diff;
        return ;
   }
   dosth(id);
   ll mid=(left+right)/2;
   update(id*2,left,mid,x,diff);
   update(id*2+1,mid+1,right,x,diff);
   st[id]=mer(st[id*2],st[id*2+1]);
}
void update1(ll id,ll left,ll right,ll x,ll y,ll val,ll val1)
{
   if (x>right||y<left) return ;
   if (x<=left&&y>=right)
   {
       modify(id,val,val1);
       return ;
   }
   dosth(id);
   ll mid=(left+right)/2;
   update1(id*2,left,mid,x,y,val,val1);
   update1(id*2+1,mid+1,right,x,y,val,val1);
   st[id]=mer(st[id*2],st[id*2+1]);
}
void build(ll id,ll left,ll right)
{
    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]);
}
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);
    }
    ll q, l;
    cin>> q>> l;
    vector<ll> vt;
    for (int i=1; i<=q; i++)
    {
        cin>> t[i]>> x[i]>> a[i];
        vt.pb(x[i]);
    }
    sort(vt.begin(),vt.end());
    vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    ll len=vt.size();
    build(1,1,len);
    ll cnt=0;
    for (int i=1;i<=q;i++)
    {
        if (t[i]==1)
        {
            cnt+=a[i];
            ll pos=lower_bound(vt.begin(),vt.end(),x[i]+1)-vt.begin()+1;
            update1(1,1,len,pos,len,a[i],0);
            pos=lower_bound(vt.begin(),vt.end(),x[i])-vt.begin()+1;
            update(1,1,len,pos,a[i]);
        }
        else
        {
            ll pos=lower_bound(vt.begin(),vt.end(),x[i]+l+1)-vt.begin()+1;
            update1(1,1,len,pos,len,-a[i],0);
            ll r=upper_bound(vt.begin(),vt.end(),x[i]+l)-vt.begin();
            ll l=lower_bound(vt.begin(),vt.end(),x[i]-l)-vt.begin()+1;
            update1(1,1,len,l,r,0,-a[i]);
        }
        ll res=0;
        for (int t=0;t<=2;t++)
        {
            res=max(res,st[1].dp[t][0][1]);
        }
       // cout <<cnt<<" "<<res<<endl;
        cout <<cnt-res<<endl;
    }
}

Compilation message (stderr)

sugar.cpp: In function 'int main()':
sugar.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sugar.cpp:134:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sugar.cpp:164:54: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
  164 |             ll l=lower_bound(vt.begin(),vt.end(),x[i]-l)-vt.begin()+1;
      |                                                  ~~~~^~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52