oj.uz

답안 #1084588

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1084588 2024-09-06T12:29:43 Z PieArmy Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
 1 ms 348 KB 
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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -