Submission #834893

#	Time	Username	Problem	Language	Result	Execution time	Memory
834893		AdamGS	Fish 2 (JOI22_fish2)	C++17	100 / 100	2151 ms	9036 KiB

fish2

#include<bits/stdc++.h> 
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const int SS=1<<17;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],n,q,seg[SS*2+10],lazy[SS*2+10],il[SS*2+10],seg3[SS*2+10];
ll seg2[SS*2+10];
vi prz;
bool deb;
void push(int v){
    seg[v*2]+=lazy[v],seg[v*2+1]+=lazy[v];
    lazy[v*2]+=lazy[v],lazy[v*2+1]+=lazy[v];
    lazy[v]=0;
}
void upd(int a,int b,int x,int p=0,int k=SS-1,int v=1){
    if(k<a or p>b) return;
    if(p>=a and k<=b){
        seg[v]+=x;
        lazy[v]+=x;
        return;
    }
    push(v);
    int sr=(p+k)/2;
    upd(a,b,x,p,sr,v*2);
    upd(a,b,x,sr+1,k,v*2+1);
    if(seg[v*2]<=seg[v*2+1]){
        seg[v]=seg[v*2];
        il[v]=il[v*2];
    }else il[v]=0;
    if(seg[v*2+1]<=seg[v*2]){
        seg[v]=seg[v*2+1];
        il[v]+=il[v*2+1];
    }
}
pair<int,int> Query(int a,int b,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return {INFi,0};
    if(p>=a and k<=b) return {seg[v],il[v]};
    int sr=(p+k)/2;
    pair<int,int> x1=Query(a,b,p,sr,v*2);
    pair<int,int> x2=Query(a,b,sr+1,k,v*2+1);
    if(x1.fi>x2.fi) swap(x1,x2);
    if(x2.fi==x1.fi) x1.se+=x2.se;
    x1.fi+=lazy[v];
    return x1;
}
void upd2(int a,int b){
    for(a+=SS;a>0;a/=2) seg2[a]+=b;
}
ll Query2(int a,int b){
    ll res=0;
    for(a+=SS-1,b+=SS+1;a/2!=b/2;a/=2,b/=2){
        if(a%2==0) res+=seg2[a+1];
        if(b%2) res+=seg2[b-1];
    }
    return res;
}
void upd3(int a,int b){
    for(seg3[a+=SS]=b,a/=2;a>0;a/=2){
        seg3[a]=max(seg3[a*2],seg3[a*2+1]);
    }
}
void uzu(int v){
    if(v>=SS){
        il[v]=1;
        if(v-SS>0 and v-SS<=n){
            seg3[v]=t[v-SS];
            seg2[v]=t[v-SS];
        }
        return;
    }
    uzu(v*2),uzu(v*2+1);
    il[v]=il[v*2]+il[v*2+1];
    seg2[v]=seg2[v*2]+seg2[v*2+1];
    seg3[v]=max(seg3[v*2],seg3[v*2+1]);
}
void baz(int a,int b,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return;
    if(p>=a and k<=b){
        prz.push_back(v);
        return;
    }
    int sr=(p+k)/2;
    baz(a,b,p,sr,v*2);
    baz(a,b,sr+1,k,v*2+1);
}
int prawy(int v,int x){
    if(v>=SS) return v-SS;
    if(seg3[v*2+1]>=x){
        return prawy(v*2+1,x);
    }return prawy(v*2,x);
} 
int lewy(int v,int x){
    if(v>=SS) return v-SS;
    if(seg3[v*2]>=x){
        return lewy(v*2,x);
    }return lewy(v*2+1,x);
}
int findr(int a,ll x){
    prz.clear(); 
    baz(a,SS-1);
    int res=-1;
    for(auto u:prz){
        if(seg3[u]>=x){
            res=lewy(u,x);
            break;
        }
    }
    return res;
}
int findl(int a,ll x){
    prz.clear();
    baz(0,a);
    int res=-1;
    for(int i=prz.size()-1;i>=0;i--){
        int u=prz[i];
        if(seg3[u]>=x){
            res=prawy(u,x);
            break;
        }
    }
    return res;
}
vi prawo(int a){
    vi res;
    res.push_back(a);
    ll curr=t[a];
    while(1){
        int xd=findr(a+1,curr);
        if(xd==-1) break;
        curr+=Query2(a+1,xd);
        if(t[xd]>curr-t[xd])
            res.push_back(xd);
        a=xd;
    }
    return res;
}
vi lewo(int a){
    vi res;
    res.push_back(a);
    ll curr=t[a];
    while(1){
        int xd=findl(a-1,curr);
        if(xd==-1) break;
        curr+=Query2(xd,a-1);
        if(t[xd]>curr-t[xd])
            res.push_back(xd);
        a=xd;
    }
    return res;
}
bool check(int a,int b){
    if(b-a<=1) return 0;
    ll xd=Query2(a+1,b-1);
    return (t[a]>xd and t[b]>xd);
}
void dod(int a,int b,int x){
    vi l;
    l.push_back(a);
    vi r;
    r.push_back(b);
    if(b!=n){
        vi xdd=prawo(b+1);
        for(auto u:xdd) r.push_back(u);
    }
    if(a!=1){
        vi xdd=lewo(a-1);
        for(auto u:xdd) l.push_back(u);
    }
    vl kol;
    kol.push_back(0);
    for(int i=1;i<r.size();i++){
        kol.push_back(Query2(r[i-1],r[i]-1));
    }
    ll curr=Query2(a+1,b-1);
    for(int i=0;i<l.size();i++){
        ll curr2=0;
        for(int i2=0;i2<r.size();i2++){
            curr2+=kol[i2];
            if(a==b and i==0 and i2==1){
                curr2-=t[a];
            }
            if(r[i2]-l[i]>1 and t[r[i2]]>curr+curr2 and t[l[i]]>curr+curr2){
                upd(l[i]+1,r[i2]-1,x);
            }
        }
        if(i!=l.size()-1){
            curr+=Query2(l[i+1]+1,l[i]);
        }
        if(a==b and i==0) curr-=t[a];
    }
}
void zm(int a,int b){
    dod(a,a,-1);
    upd2(a,b-t[a]);
    t[a]=b;
    upd3(a,t[a]);
    //deb=1;
    dod(a,a,1);
}
int ans(int a,int b){
    int a2=a,b2=b;
    int res=0;
    if(a>1 and b<n){
        dod(a-1,b+1,-1);
    }
    vi r=prawo(a);
    for(int i=r.size()-1;i>=0;i--){
        if(r[i]-a<1) continue;
        ll sum=Query2(a,r[i]-1); 
        if(t[r[i]]>sum and r[i]<=b){
            a=r[i];
            break;
        }
    }
    vi l=lewo(b);
    for(int i=l.size()-1;i>=0;i--){
        if(b-l[i]<1) continue;
        ll sum=Query2(l[i]+1,b);
        if(t[l[i]]>sum and l[i]>=a){
            b=l[i];
            break;
        }
    }
    if(a<=b){
        pair<int,int> xd=Query(a,b);
        if(xd.fi==0) res+=xd.se;
    }
    if(a2>1 and b2<n){
        dod(a2-1,b2+1,1);
    }
    return res;
}
int wint(){
    bool m=0;
    int res=0;
    char c;
    c=getchar();
    while(1){
        if(c=='-'){
            m=1;
            break;
        }
        if(int(c)-48>=0 and int(c)-48<=9){
            res+=int(c)-48;
            break;
        }
        c=getchar();
    }
    while(1){
        c=getchar();
        if(int(c)-48<0 or int(c)-48>9) break;
        res=res*10+int(c)-48;
    }
    if(m) return -res;
    return res;
}
void solve(){
    //cin>>n;
    n=wint();
    for(int i=1;i<=n;i++){
        //cin>>t[i];
        t[i]=wint();
    }
    uzu(1);
    for(int i=1;i<=n-1;i++){ 
        vi pr=prawo(i+1);
        for(int i2=1;i2<pr.size();i2++){
            if(check(i,pr[i2])){
                upd(i+1,pr[i2]-1,1);
            }
        }
    }
    //cin>>q;
    q=wint();
    for(int i=1;i<=q;i++){
        int xd;
        //cin>>xd;
        int a,b;
        xd=wint();
        a=wint(),b=wint();
        if(xd==1){
            zm(a,b);
        }else{
            cout<<ans(a,b)<<"\n"; 
        }
    }
}
int main(){
    int tt=1;
    while(tt--) solve();
}

Compilation message (stderr)

fish2.cpp: In function 'void dod(int, int, int)':
fish2.cpp:185:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |     for(int i=1;i<r.size();i++){
      |                 ~^~~~~~~~~
fish2.cpp:189:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |     for(int i=0;i<l.size();i++){
      |                 ~^~~~~~~~~
fish2.cpp:191:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |         for(int i2=0;i2<r.size();i2++){
      |                      ~~^~~~~~~~~
fish2.cpp:200:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |         if(i!=l.size()-1){
      |            ~^~~~~~~~~~~~
fish2.cpp: In function 'void solve()':
fish2.cpp:281:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  281 |         for(int i2=1;i2<pr.size();i2++){
      |                      ~~^~~~~~~~~~

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