Submission #1088971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088971		damwuan	Progression (NOI20_progression)	C++14	100 / 100	805 ms	86900 KiB

Progression

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define for1(i,x,n) for(int i=x;i<=n;i++)
#define for2(i,x,n) for(int i=x;i>=n;i--)
#define int ll

typedef long long ll;
typedef pair<int,int> pii;

const ll maxn=3e5+69;
const ll mod = 1e9+7;
const ll inf = 1e18;

int n,q,d[maxn];

namespace sub2
{
    void solve()
    {
        for1(i,1,q)
        {
            int t,l,r; cin >>t>> l>> r;
            if(t==3)
            {
                int cnt=2,res=1;
                for1(i,l+1,r)
                {
                    if (i!=l+1 && d[i]-d[i-1]==d[i-1]-d[i-2])
                    {
                        cnt++;
                    }
                    else cnt=2;
                    res=max(res,cnt);
                }
                cout << res<<'\n';
            }
            else if (t==1)
            {
                int s,c;  cin >> s>>c;
                for1(i,l,r) d[i]+=s+c*(i-l);
            }
            else
            {
                int s,c;  cin >> s>>c;
                for1(i,l,r) d[i]=s+c*(i-l);
            }
        }
    }
}

namespace sub6
{
    struct Node
    {
        int al,ar,pre,suf,res,sum,sz,lazy_add,lazy_set;
        void dbg()
        {
            cerr<< al<<' '<<ar<<' '<<pre<<' '<<suf<<' '<<res<<' '<<sum<<' '<<sz<<'\n';
        }
    }st[maxn*4];
    Node Merge(const Node& l, const Node& r)
    {
        if (l.res==-1) return r;
        if (r.res==-1) return l;
        Node c;
        c.al=l.al;
        c.ar=r.ar;
        c.pre=l.pre;
        if (l.pre==l.sz && l.ar==r.al) c.pre=l.res+r.pre;
        c.suf=r.suf;
        if (r.suf==r.sz && l.ar==r.al) c.suf=r.res+l.suf;
        c.res=max(l.res,r.res);
        if (l.ar==r.al) c.res=max(c.res,l.suf+r.pre);
        c.sum=l.sum+r.sum;
        c.lazy_add=0;
        c.lazy_set=-inf;
        c.sz=l.sz+r.sz;
        return c;
    }
    void push(int id,int l,int r)
    {
        int mid=l+r>>1;
        if (st[id].lazy_set!=-inf)
        {
            int& val=st[id].lazy_set;
            st[id*2].al=val;
            st[id*2].ar=val;
            st[id*2].pre=st[id*2].suf=st[id*2].res=mid-l+1;
            st[id*2].sum=(mid-l+1)*val;
            st[id*2].lazy_add=0;
            st[id*2].lazy_set=val;

            st[id*2+1].al=val;
            st[id*2+1].ar=val;
            st[id*2+1].pre=st[id*2+1].suf=st[id*2+1].res=r-mid;
            st[id*2+1].sum=(r-mid)*val;
            st[id*2+1].lazy_add=0;
            st[id*2+1].lazy_set=val;
            val=-inf;
        }
        if (st[id].lazy_add)
        {
            int& val=st[id].lazy_add;
            st[id*2].al+=val;
            st[id*2].ar+=val;
            st[id*2].sum+=(mid-l+1)*val;
            st[id*2].lazy_add+=val;

            st[id*2+1].al+=val;
            st[id*2+1].ar+=val;
            st[id*2+1].sum+=(r-mid)*val;
            st[id*2+1].lazy_add+=val;
            val=0;
        }
    }
    void Add(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)
        {
            st[id].al+=val;
            st[id].ar+=val;
            st[id].sum+=(r-l+1)*val;
            st[id].lazy_add+=val;
            return;
        }
        int mid=l+r>>1;
        if (st[id].lazy_add || st[id].lazy_set!=inf) push(id,l,r);
        Add(u,v,val,id*2,l,mid);
        Add(u,v,val,id*2+1,mid+1,r);
        st[id]=Merge(st[id*2],st[id*2+1]);
    }
    void Set(int u,int v,int val,int id=1,int l=1,int r=n)
    {
        if (u>r || v<l) return;
//        cerr<<"skrt "<< u<<' '<<v<<" "<<id<<' '<< st[2].lazy_set<<'\n';
        if (u<=l && r<=v)
        {
            if (l==r) st[id].sz=1;
            st[id].al=val;
            st[id].ar=val;
//            cerr<<id<<' '<< l<<' '<<r<<' '<<st[4].lazy_set<<'\n';
            st[id].pre=st[id].suf=st[id].res=r-l+1;
            st[id].sum=(r-l+1)*val;
            st[id].lazy_add=0;
            st[id].lazy_set=val;
            return;
        }
        int mid=l+r>>1;
        if (st[id].lazy_add || st[id].lazy_set!=-inf) push(id,l,r);
        Set(u,v,val,id*2,l,mid);
        Set(u,v,val,id*2+1,mid+1,r);
//        cerr<<"skrt2 "<< u<<' '<<v<<" "<<id<<' '<< st[2].lazy_set<<'\n';
        st[id]=Merge(st[id*2],st[id*2+1]);
    }
    Node Get(int u,int v,int id=1,int l=1,int r=n)
    {
//        cerr<<id<<' '<<l<<' '<<r<<'\n';
        if (u>r || v<l) return {-1,-1,-1,-1,-1,-1,-1,-1,-1};
        if (u<=l && r<=v) return st[id];
        int mid=l+r>>1;
        if (st[id].lazy_add || st[id].lazy_set!=-inf) push(id,l,r);
        return Merge(Get(u,v,id*2,l,mid),Get(u,v,id*2+1,mid+1,r));
    }
    void solve()
    {
        for1(i,1,n)
        {
//        cerr<< st[2].lazy_set<<'\n';
            Set(i,i,d[i]-d[i-1]);
//            cerr << i<<' '<< d[i]-d[i-1]<<'\n';
        }
//        st[5].dbg();
//        st[3].dbg();
        for1(i,1,q)
        {
//            cerr<< "ok?\n";
            int t,l,r; cin >>t>> l>> r;
            if(t==3)
            {
//                st[3].dbg();
                if (l==r) cout <<"1\n";
                else cout << Get(l+1,r).res+1<<'\n';
            }
            else if (t==1)
            {
                int s,c;  cin >> s>>c;
                if (l<r) Add(l+1,r,c);
                Add(l,l,s);
                if (r<n) Add(r+1,r+1,-s-c*(r-l));
            }
            else
            {
                int s,c;  cin >> s>>c;
                int x=0;
                if (l>1) x=Get(1,l-1).sum;
                int y=Get(1,r+1).sum;
                if (l<r) Set(l+1,r,c);
//                cerr<< "y = "<<
//                if (l<r)cerr<< "set "<<l+1<<' '<<r<<' '<<c<<'\n';
                Set(l,l,s-x);
//                cerr<< "set "<<l<<' '<<l<<' '<<s-x<<'\n';
                if (r<n) Set(r+1,r+1,y-s-c*(r-l));
//                if (r<n)cerr<< "set "<<r+1<<' '<<r+1<<' '<<y-s-c*(r-l)<<'\n';
            }
        }
    }
}

void sol()
{
    cin >> n>>q;
    for1(i,1,n)
    {
        cin >> d[i];
    }
    sub6::solve();
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #define task "NOI20_progression"
    if (fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*
6 10
-1 -5 4 -5 -5 -5
2 1 3 1 4
1 1 2 -1 -5
2 3 3 -5 -3
2 2 6 0 0
2 5 5 -5 -2
3 3 6
1 4 6 3 4
3 1 3
2 2 6 -5 -3
2 5 5 -3 -3

*/

Compilation message (stderr)

Progression.cpp: In function 'void sub6::push(ll, ll, ll)':
Progression.cpp:86:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid=l+r>>1;
      |                 ~^~
Progression.cpp: In function 'void sub6::Add(ll, ll, ll, ll, ll, ll)':
Progression.cpp:131:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |         int mid=l+r>>1;
      |                 ~^~
Progression.cpp: In function 'void sub6::Set(ll, ll, ll, ll, ll, ll)':
Progression.cpp:153:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |         int mid=l+r>>1;
      |                 ~^~
Progression.cpp: In function 'sub6::Node sub6::Get(ll, ll, ll, ll, ll)':
Progression.cpp:165:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  165 |         int mid=l+r>>1;
      |                 ~^~
Progression.cpp: In function 'int32_t main()':
Progression.cpp:231:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  231 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:232:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  232 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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