Submission #1058093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058093		vjudge1	Fish 2 (JOI22_fish2)	C++17	100 / 100	574 ms	17020 KiB

fish2

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=1e5+69;
const ll offset=2e5;
const ll inf=1e9+3;
const int base=350;
const ll mod=998244353;
int n,a[maxn],q;

struct fentree
{
    int st[maxn];
    void Update(int u,int v)
    {
        u+=1;
        for(;u<=n+3;u+=u&-u) st[u]+=v;
    }
    int Get1(int u)
    {
        u+=1;
        int r=0;
        for(;u>0;u-=u&-u) r+=st[u];
        return r;
    }
    int Get(int l,int r) {return Get1(r)-Get1(l-1);}
}tree2;
struct segtree1
{
    int mx[maxn*4];
    void Update(int u,int v,int id=1,int l=0,int r=n+1)
    {
//        cerr<<u<<' ' << id<<' '<<l<<' '<<r<<'\n';
        if (l==r)
        {
            mx[id]=v;
            return;
        }
        int mid=l+r>>1;
        if (u<=mid) Update(u,v,id*2,l,mid);
        else Update(u,v,id*2+1,mid+1,r);
        mx[id]=max(mx[id*2],mx[id*2+1]);
    }
    int Lwalk(int u,int val,int id=1,int l=0,int r=n+1)
    {
        if (l==r)
        {
            if (mx[id]<=val) return-1;
            return l;
        }
        int mid=l+r>>1;
        if (u<=mid) return Lwalk(u,val,id*2,l,mid);
        int c=-1;
        if (mx[id*2+1]>val) c=Lwalk(u,val,id*2+1,mid+1,r);
        if (c!=-1) return c;
        if (mx[id*2] > val) return Lwalk(u,val,id*2,l,mid);
        else return -1;
    }
    int Rwalk(int u,int val,int id=1,int l=0,int r=n+1)
    {
//        if (u==5 && val==3) cerr<< id<<' '<<l<<' '<<r<<'\n';
        if (l==r)
        {
            if (mx[id]<=val) return-1;
            return l;
        }
        int mid=l+r>>1;
        if (u>mid) return Rwalk(u,val,id*2+1,mid+1,r);
        int c=-1;
//        if (u==5 && val==3) cerr<<id<<' '<<mx[id*2]<<' '<<l<<' '<<mid<< " oday\n";
        if (mx[id*2] > val) c=Rwalk(u,val,id*2,l,mid);
        if (c!=-1) return c;
        if (mx[id*2+1] > val) return Rwalk(u,val,id*2+1,mid+1,r);
        else return -1;
    }
}tree1;

struct segtree2
{
    int mn[maxn*4],st[maxn*4],lazy[maxn*4];
    void push(int id)
    {
        int& x= lazy[id];
        mn[id<<1]+=x;
        lazy[id<<1]+=x;
        mn[id<<1|1]+=x;
        lazy[id<<1|1]+=x;
        x=0;
    }
    pii Merge(pii l,pii r)
    {
        if (l.fi==r.fi) return {l.fi,l.se+r.se};
        if (l.fi<r.fi) return {l.fi,l.se};
        return {r.fi,r.se};
    }
    void Build(int id=1,int l=1,int r=n)
    {
        if (l==r)
        {
            mn[id]=0;
            st[id]=1;
            return;
        }
        int mid=l+r>>1;
        Build(id*2,l,mid);
        Build(id*2+1,mid+1,r);
        pii x=Merge({mn[id*2],st[id*2]},{mn[id*2+1],st[id*2+1]});
        mn[id]=x.fi,st[id]=x.se;
    }
    void Update(int u,int v,int val,int id=1,int l=1,int r=n)
    {
        if (u>r || v<l) return;
        if (u<=l && r<=v)
        {
            mn[id]+=val;
            lazy[id]+=val;
            return;
        }
        if (lazy[id]!=0) push(id);
        int mid=l+r>>1;
        Update(u,v,val,id<<1,l,mid);
        Update(u,v,val,id<<1|1,mid+1,r);
        pii x=Merge({mn[id*2],st[id*2]},{mn[id*2+1],st[id*2+1]});
        mn[id]=x.fi,st[id]=x.se;
    }
    pii Get(int u,int v,int id=1,int l=1,int r=n)
    {
        if (u>r || v<l) return {inf,0};
        if (u<=l && r<=v) return {mn[id],st[id]};
        if (lazy[id]!=0) push(id);
        int mid=l+r>>1;
        return Merge(Get(u,v,id<<1,l,mid),Get(u,v,id<<1|1,mid+1,r));
    }
}tree3;
vector<int> L,R;
void Lget(int u)
{
    L.clear();
    L.pb(u-1);
    if (u==1) return;
    int id=u-2;
    while (id!=-1)
    {
        int sum=tree2.Get(id+1,u-1);
        if (a[id]>sum) L.pb(id);
        sum+=a[id];
        id=tree1.Lwalk(id-1,sum);
    }
}
void Rget(int u)
{
    R.clear();
    R.pb(u+1);
    if (u==n) return;
    int id=u+2;
    while (id!=-1)
    {
        int sum=tree2.Get(u+1,id-1);
        if (a[id]>sum) R.pb(id);
        sum+=a[id];
        id=tree1.Rwalk(id+1,sum);
    }
}
void Add(int i,int val)
{
    Rget(i);
    Lget(i);
    for(int j:R)
    {
        if (j==i+1) continue;
        if (a[i]>tree2.Get(i+1,j-1))
        {
//            cerr<< i<<' '<<j<<' '<<val<<'\n';
            tree3.Update(i+1,j-1,val);
        }
    }
    for(int j:L)
    {
        if (j==i-1) continue;
        if (a[i]>tree2.Get(j+1,i-1))
        {
//            cerr<< j<<' '<<i<<' '<<val<<'\n';
            tree3.Update(j+1,i-1,val);
        }
    }
    int k,sum,last=0;
    for(int j:R)
    {
        for1(kk,last,L.size()-1)
        {
            k=L[kk];
            sum=tree2.Get(k+1,j-1);
            if (sum>=a[j]) break;
            if (sum<a[j] && sum<a[k])
            {
//                cerr<< k<<' '<<j<<' '<<val<<'\n';
                last=kk;
                tree3.Update(k+1,j-1,val);
            }
        }
    }
}
void sol()
{
    cin >> n;
    for1(i,1,n) cin  >> a[i];
    a[0]=a[n+1]=inf;
    for1(i,0,n+1)
    {
        tree1.Update(i,a[i]);
        tree2.Update(i,a[i]);
    }
    tree3.Build();
    for1(i,0,n-1)
    {
        Rget(i);
        for(int j:R)
        {
            if (j==i+1) continue;
            if (a[i]>tree2.Get(i+1,j-1))
            {
//                cerr<< i<<' '<<j<<" +1"<<'\n';
                tree3.Update(i+1,j-1,1);
            }
        }
    }
    cin >> q;
    for1(_,1,q)
    {
        int t,l,r;cin >>t>>l>>r;
        if (t==1)
        {
            Add(l,-1);
            tree1.Update(l,r);
            tree2.Update(l,-a[l]+r);
            a[l]=r;
            Add(l,1);
        }
        else
        {
            Rget(l-1);
            Lget(r+1);
            int i=upper_bound(all(R),r)-R.begin()-1;
            i=R[i];
            int j=upper_bound(all(L),l,greater<int>())-L.begin()-1;
            j=L[j];
            cout << tree3.Get(i,j).se<<'\n';

        }
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("fish2.inp","r",stdin);
//    freopen("fish2.out","w",stdout);

    int t=1;//cin >> t;
    while (t--) {
        sol();
    }
}

/*
4 12
1 2 3
1 3
2 3
2 1
1 2
1 2
1 4
1 1
1 1
2 4
2 3
1 1
3 4



*/

Compilation message (stderr)

fish2.cpp: In member function 'void segtree1::Update(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:54:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In member function 'long long int segtree1::Lwalk(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:66:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In member function 'long long int segtree1::Rwalk(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:82:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In member function 'void segtree2::Build(long long int, long long int, long long int)':
fish2.cpp:119:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In member function 'void segtree2::Update(long long int, long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:135:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In member function 'pii segtree2::Get(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:146:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |         int mid=l+r>>1;
      |                 ~^~
fish2.cpp: In function 'void Add(long long int, long long int)':
fish2.cpp:8:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define for1(i,j,k) for(int i=j;i<=k;i++)
......
  204 |         for1(kk,last,L.size()-1)
      |              ~~~~~~~~~~~~~~~~~~   
fish2.cpp:204:9: note: in expansion of macro 'for1'
  204 |         for1(kk,last,L.size()-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