Submission #1300254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300254		raymoo_	Progression (NOI20_progression)	C++17	100 / 100	858 ms	91032 KiB

Progression

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int, int>
#define bend(v) v.begin(),v.end()
#define vect vector 
#define prq priority_queue
#define umap unordered_map
#define eb emplace_back
#define pb push_back
#define pob pop_back
#define ef emplace_front
#define pf push_front
#define pof pop_front
#define el "\n"
#define deb cout<<"\nok\n";return 
#define nextl cout<<"\n"
#define lwb lower_bound 
#define upb upper_bound
#define rs resize
#define popcnt __builtin_popcount
#define clz __builtin_clz
#define ctz __builtin_ctz
#define ll long long 
#define dbl long double
#define int long long


#define FILE "ijustwannabepartofyourskibidi"
void IO(){
    if(fopen(FILE".in", "r")){
        freopen(FILE".in", "r", stdin);
        freopen(FILE".out", "w", stdout);
    }
    else if(fopen(FILE".inp", "r")){
        freopen(FILE".inp", "r", stdin);
        freopen(FILE".out", "w", stdout);
    }
}

const ll N = 3e5 + 69, MOD = 1e9+7, INF = 1000000000000000069;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

ll rand(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(rng);
}
ll pm(ll a,const ll b=MOD){return ((a%b)+b)%b;}
ll sq(ll x){return x*x;}
ll __lcm(ll a, ll b, const ll lim=LLONG_MAX){
    if(a == -1 || b == -1)return -1;
    ll g = __gcd(a,b);
    if(b/g > lim/a)return -1;
    return (a/g)*b;
}

int n, a[N], d[N], q;

struct node{
    int preval, sufval, prelen, suflen, len, mx, sum;

    void init(int pv, int sv, int pl, int sl, int l, int m, int s){
        preval = pv ;
        sufval = sv ;
        prelen = pl ;
        suflen = sl ;
        len = l ;
        mx = m ;
        sum = s;
    }

    node operator + (const node& o) const{
        node res;res.mx = max(mx, o.mx);
        if(sufval == o.preval) res.mx = max(res.mx, suflen + o.prelen);

        res.prelen = prelen;
        res.suflen = o.suflen;

        if(prelen == len && preval == o.preval){
            res.mx = max(res.mx, prelen + o.prelen); 
            res.prelen += o.prelen;
        }

        if(o.suflen == o.len && o.sufval == sufval){
            res.mx = max(res.mx, o.prelen + suflen);
            res.suflen += suflen;
        }

        res.len = len + o.len;
        res.preval = preval;
        res.sufval = o.sufval;
        res.sum = sum + o.sum;

        return res;
    }
};

struct Seggs{
    vect<int>  lz1, lz2;
    vect<node> t;
    Seggs(){
        t.rs(4*N);
        lz1.rs(4*N, 0);
        lz2.rs(4*N, INF);
        build();
    }
    void build(int l=1, int r=n-1, int id=1){
        if(l == r){
            // cout << d[l] << ' ';
            t[id].init(d[l], d[l], 1, 1, 1, 1, d[l]);
            return;
        }

        int mid = (l+r)/2;
        build(l, mid, id*2);
        build(mid+1, r, id*2+1);
        t[id] = t[id*2] + t[id*2+1];

        // cout << l << ' ' << r << ' ' << t[id].mx << ' ' << t[id].prelen << el;
    }
    void push(int l, int r, int id){

        if(lz2[id] != INF){
            t[id].preval = lz2[id];
            t[id].sufval = lz2[id];
            t[id].sum = lz2[id] * t[id].len;
            t[id].mx = t[id].prelen = t[id].suflen = t[id].len;
            if(l < r){
                lz2[id*2] = lz2[id];
                lz2[id*2+1] = lz2[id];
                lz1[id*2]     = 0;  
                lz1[id*2+1]   = 0; 
            }
            lz2[id] = INF;
        }

        t[id].preval += lz1[id];
        t[id].sufval += lz1[id];
        t[id].sum += lz1[id] * t[id].len;
        if(l < r){
            lz1[id*2] += lz1[id];
            lz1[id*2+1] += lz1[id];
        }
        lz1[id] = 0;


    }
    void add(int i, int j, int x, int l=1, int r=n-1, int id=1){
        push(l, r, id);
        if(l > j || r < i) return;
        if(i <= l && r <= j){
            lz1[id] += x;
            push(l, r, id);
            return;
        }
        int mid = (l+r)/2;
        add(i, j, x, l, mid, id*2);
        add(i, j, x, mid+1, r, id*2+1);
        t[id] = t[id*2] + t[id*2+1];
    }
    void assign(int i, int j, int x, int l=1, int r=n-1, int id=1){
        push(l, r, id);
        if(l > j || r < i) return;
        if(i <= l && r <= j){
            lz2[id] = x;
            push(l, r, id);
            // cout << "hm " << l << ' ' << r << ' ' << t[id].mx << ' ' << t[id].preval << ' ' << t[id].sufval << el;
            return;
        }
        int mid = (l+r)/2;
        assign(i, j, x, l, mid, id*2);
        assign(i, j, x, mid+1, r, id*2+1);
        t[id] = t[id*2] + t[id*2+1];
        // cout << "hm " << l << ' ' << r << " pre: " << t[id].preval << ' ' << t[id].prelen << " suf: " << t[id].sufval << ' ' << t[id].suflen << el;
    }
    int get_sum(int i, int j, int l=1, int r=n-1, int id=1){
        push(l, r, id);
        if(l > j || r < i) return 0;
        if(i <= l && r <= j){
            // cout << "interval " << l << ' ' << r << ' ' << t[id].sum << el;
            return t[id].sum;
        }
        int mid = (l+r)/2;
        return get_sum(i, j, l, mid, id*2) + get_sum(i, j, mid+1, r, id*2+1);
    }
    void get(int i, int j, vect<int>& aids, int l=1, int r=n-1, int id=1){
        push(l, r, id);
        if(l > j || r < i) return;
        if(i <= l && r <= j){
            aids.eb(id);
            return;
        }
        int mid = (l+r)/2;
        get(i, j, aids, l, mid, id*2);
        get(i, j, aids, mid+1, r, id*2+1);
    }

    int query(int l, int r){
        vect<int> aids;
        get(l, r, aids);
        int ans = 0;
        for(int i=0;aids.size()>i;i++){
            int id1 = aids[i];
            node tmp = t[id1];
            ans = max(ans, tmp.mx);
            for(int j=i+1;aids.size()>j;j++){
                int id2 = aids[j];
                tmp = tmp + t[id2];
                ans = max(ans, tmp.mx);
            }
        }
        return ans+1;
    }

};

void sol(){
    cin >> n >> q;
    for(int i=0;n>i;i++) cin >> a[i];

    if(n == 1){
        while(q--){
            int t, l, r, S, C;
            cin >> t >> l >> r;
            l--;r--;

            if(t == 1) cin >> S >> C, a[l] += S;
            else if(t == 2) cin >> S >> C, a[l] = S;
            else cout << 1 << el;
        }
        return;
    }

    for(int i=1;n>i;i++){
        d[i] = a[i] - a[i-1];
    }

    Seggs sgt;
    int a0 = a[0]; 


    // cout << q << el;
    // deb;

    auto get_single_element = [&](int i){
        if(i == 0) return a0;
        // cout << sgt.get_sum(1, i) + a << el;
        return sgt.get_sum(1, i) + a0;
    };

    while(q--){
        int t, l, r, S, C;
        cin >> t >> l >> r;
        l--;r--;
        if(t == 1) {
            cin >> S >> C;

            if(l == 0) a0 += S;

            if(l+1 <= r)
                sgt.add(l+1, r, C);

            if(l > 0) sgt.add(l, l, S);
            if(r+1 < n) sgt.add(r+1, r+1, -(S + C * (r-l)));
            
        }else if(t == 2){
            cin >> S >> C;

            int al = sgt.get_sum(1, l) + a0, ar = r<n ? sgt.get_sum(1, r) + a0 : -69; 

            if(l == 0) a0 = S;

            if(l > 0) sgt.add(l, l, -al + S);
            if(r+1<n) sgt.add(r+1, r+1, +ar - (S + C * (r-l)));

            if(l+1 <= r)
                sgt.assign(l+1, r, C);

        }else{
            cout << sgt.query(l+1, r) << el;
        }
            // for(int i=0;n>i;i++) cout << get_single_element(i) << ' ';nextl;
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);

    IO();
    int t = 1;
    // cin >> t;
    while(t--) sol();
}
/*
                                                     ...-%%%%%%%%%%%...                               
                                             .:**#%=%%%%%+........-%%%%. .                            
                                        .%%%%%%=-..%#.               .#%%.                            
                                      %%%+..      .:                    *%%.                          
                                    .%%.          :.                     :%%%%%:.                     
                                   .%%.     ...  .:                    ::     .=%%%.                  
                                 ..%%.    #%#:%. :                   :..          =%%.                
                                %%+..:  .%*::::%-::::::-::::::..   .:-%%%%.        .*%%..             
                              .%#     :.%:::::::%%%%%%%%%%%%%+...%%%+::::%#.         .%%.             
                             .%%.  ..:.%=::::*%#***#%::::::::%%%%=:::::::%%.          .%%.            
                             =%%%...-%%%:::*%********%:::%%%****%::::::::%%            .%-            
                            .%::::%%***%=:%%**********%%********%:::::::=%-:.          .%..           
                            #%:::%#*****%%**********************%:::+%%%*%%-.:      .::..%%.          
                           .%%::%%*****==**==*****#************#%%%%#******%%..::::..     .%%.        
                         .%%#%+%%***************##*+=+*==********************%%.:.         .%%        
                        .%%***%%****************#**==**==******==**+=+********%%%%%%%%%     %%.       
                      .#%#*********************%%**************++************%%::::::%*   .%%%.       
                     .%%***************#*****%%%****************************%%::::::%% .-%%%.         
                    .#%***************#****%%--%*********%*****************%#::::-%%%%%%%%%%.         
                    .%%**************#**%%%----%********%%**************#***#%%%#**%#******%*         
                   .%%**************#%%%--.....%%*******%%**************#**********#%******%%.        
                   .%%*************%%...........%%******%-%*************#***********%%*****%%.        
                   .%%*************%%...%%%%%.....%%%%%%%.=%%%%%%%%##****#****##::::+%%*****%#        
                   .%%************%%...%.   %%.................%%%%-.....%*****#*****%%*****%%        
                   .#%#*#****#****%%:::%-  %%.................%.   #-....%*****#*#####%#****%%.       
                    .%%##****%%%**%%:::::##...................%=  .%+:::%#*****#:####*%%****%%.       
                     .+%%#**%%.#%%%%::::::........###+.:*##-....%%%:::::%*****##******%%****%%-       
                       ..%%*%%.......:::.......##..#*...#+..#*....:::::%******#*****##%%*****%%.      
                        .%%%%%................#-##=--##+-+###-#....:::%******#:###*::%%#*****%%.      
                      .%%****%%..............#----------------=*...#%#****##**##::#**%%*******%%.     
                      .%%%%%*=+%%*...........#-----------------#.....#%%%%%%+:##*##:*%%*******%%%.    
                        ..:*%====%%%%........#-----------------#:.........%#********%%*****%%%%%%.    
                          .%%=======*%%%%%%%.%%+----#-%------%%#.......%%%%::::::::%%==***#%###%%.    
                         ..%%=============+%%-:#%%%%-::%%%%%%::%%%%%%%%%=%%*******%%=====**%%###%%..  
                        -%%%%%%%%%%%%%%%%+%.%+:+%::%::::%::%:::%%#%... .%%******%%%========#%####%%.  
                      .%%++#############%%# ..%%.**%%#%%%%%%%#%***%.  :%%*****%%%=+%%%%%%%%%%#####%%. 
                    .%%++++*############*++%   .%************#****%.  #%*%%%%+++%%%%###############%%.
         .+%%%%%%%%%%####+##########*+++++%%. .%**#**********#****%   %%**%%%++++###################%:
      =%%%%######################++++++++%%*%.-%%#***********#****% .%****%%+++++###################%%
   .%%%#######################*%%%%%%%%.%%*#%+%###################%.%%***%%%+++++###################%%
  *%%######################+#%%++++++%*. =%*%. .:%%%%########%%%%%%%%%#*#%.%%++#####################%%
.%%%#####################%%%%%+++++++%-  %*#%%.          .%%%*++++++*%%%....%%#####################%%*
%%######%%%%%#%%%%%######%%.%*+++++++%.  %****#.        .%%+++*+++++*++%%...=%%###################%%%.
%%%%%%%%#-=##%...%%######%%.%%+++++++%%..*%***#%%%%%. ..%+++++++++++++++%%...%%##################%%%. 
.%:.             .#%#####%%.%%+++++++++%. %*********%%%%%++++++++++++++++%%...%%##############%%%%..  
                  :%#####%% .%%+++++++%%  .%%**********%%++++++++++++++++%%.....%#########%%%%%% .    
                 *%#####%%.  .%%+++++++%%:. .%%********%%++++++++++++++++%%....%%%%%%%%%%%%*..        
                 .%%##%%%     .%%*+++++++%%. ..#%%%#****%%+++++++++++++++%%%%%% . .....               
                 %%#%%%.       .:%%%%%%%%%%%...-%. ......%%+++++++++++++%%.                           
               ..%%%.              ...     .%%%#%%%=:#%%%%%%%%*++++++%%%#                             
                                                 .-%%+.  ... .%%%%%%%:.  
*/

Compilation message (stderr)

Progression.cpp: In function 'void IO()':
Progression.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen(FILE".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen(FILE".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(FILE".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(FILE".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