Submission #788657

#	Time	Username	Problem	Language	Result	Execution time	Memory
788657		8pete8	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	5 ms	3380 KiB

Main

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<pii,pii>
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
const int mxn=2*1e5+1,mx=1e6;
#define int long long
int seg[2*mxn+10],d[mxn+10],seg2[2*mxn+10];
int n,h;
void ap(int val,int pos){
    seg[pos]+=val;
    seg2[pos]+=val;
    if(pos<n)d[pos]+=val;
}
void build(int pos){for(;pos>1;pos>>=1)seg[pos>>1]=max(seg[pos],seg[pos^1])+d[pos>>1],seg2[pos>>1]=min(seg2[pos],seg2[pos^1])+d[pos>>1];}
void upd(int pos,int val){
    pos+=n;
    seg[pos]=max(seg[pos],val);
    seg2[pos]=min(seg[pos],val);
    for(;pos>1;pos>>=1)seg[pos>>1]=max(seg[pos],seg[pos^1]),seg2[pos>>1]=min(seg2[pos],seg2[pos^1]);
}
void pop(int pos){
    for(int s=h;s>0;s--){
        int i=pos>>s;
        if(d[i]){
            ap(d[i],i<<1);
            ap(d[i],(i<<1)^1);
            d[i]=0;
        }
    }
}
void add(int l,int r,int val){
    int cl=l+n,cr=r+n;
    for(l+=n,r+=n;l<=r;l>>=1,r>>=1){     
        if(l&1)ap(val,l++);
        if(!(r&1))ap(val,r--);
    }
    build(cl);
    build(cr);
}
pii qry(int l,int r){   
    pop(l+n);
    pop(r+n);
    int ans=INT_MIN,ans2=INT_MAX;
    for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
        if(l&1){
            ans=max(ans,seg[l]);
            ans2=min(ans2,seg2[l]);
            l++;
        }
        if(!(r&1)){
            ans=max(ans,seg[r]);
            ans2=min(ans2,seg2[r]);
            r--;
        }
    }
    return {ans,ans2};
}
int32_t main(){
    int q;
    cin>>n>>q;
    vector<int>v(n);
    for(int i=0;i<=30;i++)if(n&(1<<i))h=i;
    for(int i=0;i<n;i++)cin>>v[i];
    for(int i=0;i<2*mxn;i++)seg2[i]=INT_MAX;
    for(int i=0;i<n;i++)upd(i,v[i]);
    while(q--){
        int l,r,x;cin>>l>>r>>x;
        add(--l,--r,x);
        int last=0,sum=0;
        for(int i=0;i<n-1;i++){
            pii a=qry(last,i),b=qry(i+1,n-1),c=qry(last,n-1);
            if((a.f-a.s)+(b.f-b.s)>c.f-c.s){
                sum+=(a.f-a.s);
                last=i+1;
            }
        }
        pii tmp=qry(last,n-1);
        sum+=tmp.f-tmp.s;
        cout<<sum<<'\n';
    }
}

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