Submission #1084588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084588		PieArmy	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	348 KiB

Main

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

struct Seg{
	int n;
	vector<ll>sum,ek,arr;
	vector<int>sol,sag;
	void comb(int node,int left,int right){
		sum[node]=sum[node*2]+sum[node*2+1];
		ek[node]=ek[node*2];
		sol[node]=sol[node*2];
		if(sol[node*2]==0)sol[node]=sol[node*2+1];
		sag[node]=sag[node*2+1];
		if(sag[node*2+1]==0)sag[node]=sag[node*2];
		if(sol[node*2+1]+sag[node*2]){
			sum[node]+=ek[node*2+1];
		}
	}
	void build(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			sum[node]=0;
			if(arr[left]<0)sol[node]=-1;
			if(arr[left]==0)sol[node]=0;
			if(arr[left]>0)sol[node]=1;
			sag[node]=sol[node];
			ek[node]=abs(arr[left]);
			return;
		}
		build(node*2,left,mid);build(node*2+1,mid+1,right);
		comb(node,left,right);
	}
	Seg(vector<ll>v){
		arr=v;
		n=arr.size();
		sum.resize(n<<2);
		ek.resize(n<<2);
		sol.resize(n<<2);
		sag.resize(n<<2);
		build();
	}
	ll tar,x;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			arr[left]+=x;
			sum[node]=0;
			if(arr[left]<0)sol[node]=-1;
			if(arr[left]==0)sol[node]=0;
			if(arr[left]>0)sol[node]=1;
			sag[node]=sol[node];
			ek[node]=abs(arr[left]);
			return;
		}
		if(tar>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		comb(node,left,right);
	}
	void update(ll l,ll r){
		tar=l;
		x=r;
		up();
	}
};

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	int n,q;cin>>n>>q;
	vector<ll>v;
	ll las;cin>>las;v.pb(0);
	for(int i=1;i<n;i++){
		ll x;cin>>x;
		v.pb(x-las);
		las=x;
	}
	Seg seg(v);
	while(q--){
		int l,r;ll x;
		cin>>l>>r>>x;
		if(l!=1){
			seg.update(l-1,x);
		}
		if(r!=n){
			seg.update(r,-x);
		}
		cout<<seg.sum[1]<<endl;
	}
}

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