Submission #564337

#	Time	Username	Problem	Language	Result	Execution time	Memory
564337		fcmalkcin	Ants and Sugar (JOI22_sugar)	C++17	100 / 100	1816 ms	128164 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[2][2];
    ll la;
    ll la1;
    tk()
    {
        la=0;
        la1=0;
        for (int t=0; t<=1; t++)
            for (int t1=0; t1<=1; t1++)
                dp[t][t1]=-base;
    }
};
tk st[4*maxn];
void modify(ll id,ll val,ll val1)
{
    st[id].dp[0][0]-=val;
    st[id].dp[1][1]+=(val+val1);
    st[id].dp[0][1]+=val1;
    st[id].dp[1][0]+=val1;
    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 l=0; l<=1; l++)
    {
        for (int r=0; r<=1; r++)
        {
            ll l1=1-r;
            for (int r1=0; r1<=1; r1++)
            {
                c.dp[l][r1]=max(max(max(a.dp[l][r1],b.dp[l][r1]),c.dp[l][r1]),a.dp[l][r]+b.dp[l1][r1]);
            }
        }
    }
    return c;
}
void update1(ll id,ll left,ll right,ll x,ll y,ll val,ll val1)
{
    // if (left==1&&right==4) cout <<x<<" "<<y<<" "<<val<<" "<<val1<<" wtf"<<endl;
    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)
    {
       st[id].dp[0][1]=0;
       st[id].dp[0][0]=0;
       st[id].dp[1][1]=0;
        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 get(ll id,ll left,ll right)
{
// for (int t=0;t<=1;t++) for (int t1=0;t1<=1;t1++) cout <<st[id].dp[t][t1]<<" "<<id<<" "<<t<<" "<<t1<<" chk2"<<endl;
    if (left==right)
        return ;
    dosth(id);
    ll mid=(left+right)/2;
    get(id*2,left,mid);
    get(id*2+1,mid+1,right);
  //  st[id]=mer(st[id*2],st[id*2+1]);
    /*auto p=mer(st[id*2],st[id*2+1]);
    for (int t=0;t<=1;t++)
    {
        for (int t1=0;t1<=1;t1++)
        {

        }
    }*/
}
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;
            update1(1,1,len,pos,pos,0,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);
            /*if (i==2)
            {
                cout <<pos<<" "<<len<<" wtf"<<endl;
            }*/

            ll rt=upper_bound(vt.begin(),vt.end(),x[i]+l)-vt.begin();
            ll lf=lower_bound(vt.begin(),vt.end(),x[i]-l)-vt.begin()+1;
            //    cout <<lf<<" "<<rt<<" "<<vt.size()<<" "<<x[i]+l+1<<" chk1"<<endl;
            update1(1,1,len,lf,rt,0,-a[i]);
        }
        /*get(1,1,len);
        if (i==3)
        {
            cout <<st[2].dp[0][0]<<" "<<st[3].dp[1][1]<<" chkwtf"<<endl;
            for (int h=4; h<=7; h++)
            {
                for (int t=0; t<=1; t++)
                    for (int t1=0; t1<=1; t1++)
                        cout <<st[h].dp[t][t1]<<" "<<h-3<<" "<<t<<" "<<t1<<" wtf3"<<endl;
            }
        }*/
        ll res=0;
        res=max(res,st[1].dp[0][1]);
        //   cout <<st[1].dp[0][1]<<" wtf"<<endl;
        /*if (i==3)
        {

            cout <<cnt<<" "<<res<<" chk1"<<endl;
        }*/
        // auto p=mer(st[2],st[3]);
        // cout <<p.dp[0][1]<<" wtfchk3"<<endl;
        cout <<cnt-res<<endl;
    }
}

Compilation message (stderr)

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

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