Submission #1017434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017434		modwwe	Fish 2 (JOI22_fish2)	C++17	100 / 100	1064 ms	408256 KiB

fish2

//https://www.instagram.com/_modwwe/
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<"cuuuuuuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e18;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
int sa,sb;
main()
{
#ifndef ONLINE_JUDGE
    //    fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo(),down
}
struct IT
{
    int sl,sr;/// size left
    /// size right
    ic cr[32];
    ic cl[32];
    int c,d;
    int a;
} t[400001],ans;
int a[100001];
vector<id> v;
bool cmp(id a,id b)
{
    return a.a<b.a;
}
IT mer(int y,int z,int mid,int l,int r)
{
    IT tx;
    v.clear();
    for(int i=0; i<=t[z].sl; i++)
        v.pb({a[t[z].cl[i].b]-t[z].cl[i].a,t[z].cl[i].a,t[z].cl[i].b,i});
    sort(v.begin(),v.end(),cmp);
    s4=-1 ;
    mx=t[y].sr+1;
    s5=-1;
    s6=-1;
    for(auto x:v )
    {
        while(mx>0&&t[y].cr[mx-1].a<x.a)s5=max(s5,a[t[y].cr[mx-1].b]-t[y].cr[mx-1].a),mx--;
        if(s5>x.b)
        {
            s4=max(s4,x.c);
            if(s4==x.c)
                s6=x.d;
        }
    }
    tx.d=t[z].d;
    s9=t[z].d;
    if(s4!=-1) tx.d+=s4-mid-t[z].cl[s6].c-1,s9+=s4-mid-t[z].cl[s6].c-1;
    s10=s4;
    v.clear() ;
    for(int i=0; i<=t[y].sr; i++)
        v.pb({a[t[y].cr[i].b]-t[y].cr[i].a,t[y].cr[i].a,t[y].cr[i].b,i});
    sort(v.begin(),v.end(),cmp);
    s4=n+1;
    mx=-1;
    s5=-1;
    s6=0;
    for(auto x:v)
    {
        while(mx<t[z].sl&&t[z].cl[mx+1].a<x.a)
            mx++,s5=max(s5,a[t[z].cl[mx].b]-t[z].cl[mx].a);
        if(s5>x.b)
        {
            s4=min(s4,x.c);
            if(s4==x.c) s6=x.d;
        }
    }
    s8=t[y].d;
    tx.d+=t[y].d;
    if(s4!=n+1)tx.d+=mid-s4-t[y].cr[s6].c,s8+=mid-s4-t[y].cr[s6].c;
    bool dl=0;
    bool dr=0;
    dem=-1;
    for(int i=0; i<=t[y].sl; i++)
        tx.cl[++dem]=t[y].cl[i];
    sa=-1;
    for(int i=0; i<=t[z].sl; i++)
        if(t[z].cl[i].a+t[y].a<a[t[z].cl[i].b])
        {
            tx.cl[++dem]=t[z].cl[i],
                         dl=1;
            if(s10!=-1)
            {
                if(t[z].cl[i].b<s10)
                {
                    tx.cl[dem].c=t[z].cl[i].b-mid;
                }
                else tx.cl[dem].c+=s9-t[z].d;
            }
            tx.cl[dem].c+=s8;
            tx.cl[dem].a+=t[y].a;
        }
    sa=dem;
//if(l==1&&r==3)cout<<t[y].d,down
    tx.sl=dem;
    dem=-1;
    sb=n+1;
    for(int i=0; i<=t[y].sr; i++)
        if(t[y].cr[i].a+t[z].a<a[t[y].cr[i].b])
        {
            tx.cr[++dem]=t[y].cr[i],
                         tx.cr[dem].a+=t[z].a,
                                       dr=1;
            if(s4!=n+1)
            {
                if(s4<t[y].cr[i].b)tx.cr[dem].c=mid-t[y].cr[i].b+1;
                else tx.cr[dem].c+=s8-t[y].d;
            }
            tx.cr[dem].c+=s9;
        }
    for(int i=0; i<=t[z].sr; i++)
        tx.cr[++dem]=t[z].cr[i];
    sb=0;
    tx.c=s9-tx.cl[sa].c+tx.cl[sa].b-l;
    tx.c+=s8-tx.cr[sb].c+r-tx.cr[sb].b;
    tx.a=t[y].a+t[z].a;
    tx.sr=dem;
    return tx;
}
void build(int node,int l,int r)
{
    if(l==r)
    {
        t[node].cr[0]=t[node].cl[0]= {0,l};
        t[node].a=a[l];
        return;
    }
    int mid=l+r>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    t[node]=mer(node<<1,node<<1|1,mid,l,r);
}
void upd(int node,int l,int r,int l1)
{
    if(l==r)
    {
        t[node].cr[0]=t[node].cl[0]= {0,l};
        t[node].a=a[l];
        return;
    }
    int mid=l+r>>1;
    if(l1<=mid) upd(node<<1,l,mid,l1);
    else upd(node<<1|1,mid+1,r,l1);
    t[node]=mer(node<<1,node<<1|1,mid,l,r);

}
void get(int node,int l,int r, int l1,int r1)
{
    if(l>r1||r<l1) return ;
    if(l>=l1&&r<=r1)
    {
        if(l==l1) t[0]=t[node];
        else t[0]=mer(0,node,l-1,l1,r);
        return;
    }
    int mid=l+r>>1;
    get(node<<1,l,mid,l1,r1);
    get(node<<1|1,mid+1,r,l1,r1);
}
void phongbeo()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    build(1,1,n);
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>l;
        if(l==1)
        {
            cin>>l>>r;
            a[l]=r;
            upd(1,1,n,l);
        }
        else
        {
            t[0].sl=-1;
            t[0].sr=-1;
            cin>>l>>r;
            get(1,1,n,l,r);
            cout<<r-l+1-t[0].c,down
        }
    }

}

Compilation message (stderr)

fish2.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main()
      | ^~~~
fish2.cpp: In function 'IT mer(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:120:10: warning: variable 'dl' set but not used [-Wunused-but-set-variable]
  120 |     bool dl=0;
      |          ^~
fish2.cpp:121:10: warning: variable 'dr' set but not used [-Wunused-but-set-variable]
  121 |     bool dr=0;
      |          ^~
fish2.cpp: In function 'void build(long long int, long long int, long long int)':
fish2.cpp:177:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  177 |     int mid=l+r>>1;
      |             ~^~
fish2.cpp: In function 'void upd(long long int, long long int, long long int, long long int)':
fish2.cpp:190:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  190 |     int mid=l+r>>1;
      |             ~^~
fish2.cpp: In function 'void get(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:205:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  205 |     int mid=l+r>>1;
      |             ~^~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17