Submission #438212

#	Time	Username	Problem	Language	Result	Execution time	Memory
438212		leaked	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	17 ms	25272 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define f first
#define s second
#define endl '\n'
#define vec vector
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define m_p make_pair
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define int long long

using namespace std;
using namespace __gnu_pbds;

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

auto rng=bind(uniform_int_distribution<int>(0,1e9),mt19937(time(0)));

template<class T>bool umin(T &a,const T &b) {return (a>b?a=b,1:0);}
template<class T>bool umax(T &a,const T &b) {return (a<b?a=b,1:0);}

template<class T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=1e5+1;
struct tr{
    array<int,3> pref,suf;///mx,mn,size
    int sz,ans;
    tr(){
        sz=0;ans=0;
        for(int i=0;i<3;i++) pref[i]=suf[i]=0;
    }
};
bool can(int x,int y,int a,int b){
    return max(x,a)-min(y,b)>x-y+a-b;
}
tr mg(const tr &a,const tr &b){
    tr c;
    c.ans=a.ans+b.ans;
    c.sz=a.sz+b.sz;
    c.pref=a.pref;
    c.suf=a.suf;
    if(can(a.suf[0],a.suf[1],b.pref[0],b.pref[1])){
        c.ans-=b.pref[0]-b.pref[1];
        c.ans-=b.suf[0]-b.suf[1];
        c.ans+=max(a.suf[0],b.pref[0])-min(a.suf[1],b.pref[1]);
//        cerr<<"HERE" <<endl;
        if(a.suf[2]==a.sz){
            c.pref[0]=max(a.pref[0],b.pref[0]);
            c.pref[1]=min(a.pref[1],b.pref[1]);
            c.pref[2]=a.pref[2]+b.pref[2];
        }
        if(b.pref[2]==b.sz){
            c.suf[0]=max(a.suf[0],b.suf[0]);
            c.suf[1]=min(a.suf[1],b.suf[1]);
            c.suf[2]=a.suf[2]+b.suf[2];
        }
    }
    return c;
}
tr t[4*N];
void add(int id,int x,int v,int tl,int tr){
    if(tl==tr){
        for(int i=0;i<2;i++) t[v].pref[i]=t[v].suf[i]=x;
        t[v].pref[2]=t[v].suf[2]=1;
        t[v].sz=1;
        return;
    }
    int tm=(tl+tr)>>1;
    if(tm>=id) add(id,x,2*v,tl,tm);
    else add(id,x,2*v+1,tm+1,tr);
    t[v]=mg(t[2*v],t[2*v+1]);
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    vec<int>a;
    for(int i=0;i<n;i++){
        int x;cin>>x;add(i,x,1,0,n-1);
        a.pb(x);
    }
    while(q--){
        int l,r,x;
        cin>>l>>r>>x;--l;--r;
        for(int j=l;j<=r;j++){
            add(j,a[j]+x,1,0,n-1);
            a[j]+=x;
        }
        cout<<t[1].ans<<endl;
    }
    return  0;
}
/*

*/

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55