Submission #1133738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133738		Aviansh	Progression (NOI20_progression)	C++20	9 / 100	121 ms	39752 KiB

Progression

#include <bits/stdc++.h>

using namespace std;

struct node{
    int lval,rval,lcn,rcn,len,best;
    bool operator==(node a){
        return (a.lval==lval&&a.rval==rval&&lcn==a.lcn&&a.rcn==rcn&&a.len==len&&a.best==best);
    }
};

struct lazynode{
    int add,fix;
    bool toadd,tofix;
};

void print(node a){
    cout << a.lval << " " << a.lcn << " " << a.rval << " " << a.rcn << " " << a.len << " " << a.best << "\n";
}

struct segTree{
    node *st;
    lazynode *laz;
    node defnode;
    lazynode lazdef;
    int n;

    node unite(node a, node b){
        if(a==defnode){
            return b;
        }
        if(b==defnode){
            return a;
        }
        node ans = defnode;
        ans.lval=a.lval;
        ans.rval=b.rval;
        ans.best=max(a.best,b.best);
        ans.len=a.len+b.len;
        ans.lcn=a.lcn;
        ans.rcn=b.rcn;
        if(a.rval==b.lval){
            if(a.lcn==a.len){
                ans.lcn=a.len+b.lcn;
            }
            if(b.rcn==b.len){
                ans.rcn=b.len+a.rcn;
            }
            ans.best=max(ans.best,a.rcn+b.lcn);
        }
        ans.best=max({ans.best,ans.lcn,ans.rcn});
        return ans;
    }

    segTree(int siz){
        int x = (int)ceil(log2(siz));
        x++;
        st=new node[(1<<x)];
        laz=new lazynode[(1<<x)];
        n=siz-1;
        defnode.lval=0;
        defnode.rval=0;
        defnode.lcn=0;
        defnode.rcn=0;
        defnode.len=0;
        defnode.best=0;
        lazdef.toadd=0;
        lazdef.tofix=0;
        lazdef.add=0;
        lazdef.fix=0;
        fill(st,st+(1<<x),defnode);
        fill(laz,laz+(1<<x),lazdef);
    }
    void push(int ind, int l, int r){
        if(laz[ind].tofix){
            st[ind].lval=laz[ind].fix;
            st[ind].rval=laz[ind].fix;
            st[ind].lcn=(r-l+1);
            st[ind].rcn=(r-l+1);
            st[ind].len=(r-l+1);
            st[ind].best=(r-l+1);
        }
        if(laz[ind].toadd){
            st[ind].lval+=laz[ind].add;
            st[ind].rval+=laz[ind].add;
        }
        if(l==r){
            laz[ind].toadd=0;
            laz[ind].tofix=0;
            laz[ind].add=0;
            laz[ind].fix=0;
            return;
        }
        if(laz[ind].tofix){
            laz[2*ind+1].toadd=0;
            laz[2*ind+1].tofix=1;
            laz[2*ind+1].add=0;
            laz[2*ind+1].fix=laz[ind].fix;
            laz[2*ind+2].toadd=0;
            laz[2*ind+2].tofix=1;
            laz[2*ind+2].add=0;
            laz[2*ind+2].fix=laz[ind].fix;
        }
        if(laz[ind].toadd){
            laz[2*ind+1].toadd=1;
            laz[2*ind+1].add+=laz[ind].add;
            laz[2*ind+2].toadd=1;
            laz[2*ind+2].add+=laz[ind].add;
        }
        laz[ind].toadd=0;
        laz[ind].tofix=0;
        laz[ind].add=0;
        laz[ind].fix=0;
    }

    void updateFix(int s, int e, int val, int l, int r, int ind){
        push(ind,l,r);
        if(s<=l&&r<=e){
            laz[ind].tofix=1;
            laz[ind].toadd=0;
            laz[ind].add=0;
            laz[ind].fix=val;
            push(ind,l,r);
            return;
        }
        if(s>r||e<l){
            return;
        }
        int mid = (l+r)/2;
        updateFix(s,e,val,l,mid,ind*2+1);
        updateFix(s,e,val,mid+1,r,ind*2+2);
        push(2*ind+1,l,mid);
        push(2*ind+2,mid+1,r);
        st[ind]=unite(st[ind*2+1],st[ind*2+2]);
    }

    void updateAdd(int s, int e, int val, int l,int r,int ind){
        push(ind,l,r);
        if(s<=l&&r<=e){
            laz[ind].toadd=1;
            laz[ind].add=val;
            push(ind,l,r);
            return;
        }
        if(s>r||e<l){
            return;
        }
        int mid = (l+r)/2;
        updateAdd(s,e,val,l,mid,ind*2+1);
        updateAdd(s,e,val,mid+1,r,ind*2+2);
        push(2*ind+1,l,mid);
        push(2*ind+2,mid+1,r);
        st[ind]=unite(st[ind*2+1],st[ind*2+2]);
    }

    node query(int s, int e, int l,int r, int ind){
        push(ind,l,r);
        if(s<=l&&r<=e){
            return st[ind];
        }
        if(s>r||e<l){
            return defnode;
        }
        int mid = (l+r)/2;
        return unite(query(s,e,l,mid,ind*2+1),query(s,e,mid+1,r,ind*2+2));
    }
};

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    segTree st(n-1);
    int arr[n];
    for(int i = 0;i<n;i++){
        cin >> arr[i];
    }
    int ans = 0;
    int curr= 0;
    int prev=-1e9;
    for(int i = 1;i<n;i++){
        if(arr[i]-arr[i-1]==prev){
            curr++;
        }
        else{
            curr=1;
            prev=arr[i]-arr[i-1];
        }
        ans=max(curr,ans);
    }
    ans++;
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            int l,r,s,c;
            cin >> l >> r >> s >> c;
        }
        if(t==2){
            int l,r,s,c;
            cin >> l >> r >> s >> c;
            ans=n;
        }
        if(t==3){
            int l,r;
            cin >> l >> r;
            cout << ans << "\n";
        }
    }
    return 0;
    //sub2:
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            int l,r,s,c;
            cin >> l >> r >> s >> c;
            l--;r--;
            for(int i = l;i<=r;i++){
                arr[i]+=s+(i-l)*c;
            }
        }
        if(t==2){
            int l,r,s,c;
            cin >> l >> r >> s >> c;
            l--;r--;
            for(int i = l;i<=r;i++){
                arr[i]=s+(i-l)*c;
            }
        }
        if(t==3){
            int l,r;
            cin >> l >> r;
            l--;r--;
            if(l==r){
                cout << 1 << "\n";
                continue;
            }
            int ans = 1;
            int curr = 0;
            int prev = -1e9;
            for(int i = l+1;i<=r;i++){
                if(arr[i]-arr[i-1]==prev){
                    curr++;
                }
                else{
                    curr=1;
                    prev=arr[i]-arr[i-1];
                }
                ans=max(curr,ans);
            }
            cout << ans+1 << "\n";
        }
    }
    return 0;
    for(int i = 1;i<n;i++){
        st.updateFix(i-1,i-1,arr[i]-arr[i-1],0,n-2,0);
    }
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            int l,r,s,c;
            cin >> l >> r >> s >> c;
            l--;r--;
            st.updateAdd(l,r-1,c,0,n-2,0);
            if(l){
                st.updateAdd(l,l,s,0,n-2,0);
            }
            if(r<=n-2){
                st.updateAdd(r,r,-s,0,n-2,0);
            }
        }
        if(t==2){
            int l,r,s,c;
            cin >> l >> r >> s >> c;
            l--;r--;
            cout << "oh no\n";
        }
        if(t==3){
            int l,r;
            cin >> l >> r;
            l--;r--;
            if(l==r){
                cout << 1 << "\n";
                continue;
            }
            cout << st.query(l,r-1,0,n-2,0).best+1 << "\n";
        }
    }
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 15
• Subtask 3: 0 / 35
• Subtask 4: 0 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17