oj.uz

답안 #1045351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1045351 2024-08-05T21:00:07 Z KarolZ Sjeckanje (COCI21_sjeckanje) C++14
0 / 110
 3 ms 16988 KB 
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=(1<<18);
ll t[2*maxn+1];//wyniki
pair<bool,bool>bb[2*maxn+1];//w ktora strone
pair<ll,ll>tp[2*maxn+1];//krancowe wartosci
ll l[2*maxn+1];//ile zepchnac w dol
pair<int,int>p[2*maxn+1];
void prz(int v,int x,int y){
	p[v]={x,y};
	if(x==y)return;
	prz(2*v,x,(x+y)/2);
	prz(2*v+1,(x+y)/2+1,y);
	return;
}
void lazy(int v){
	tp[2*v].first+=l[v];
	tp[2*v].second+=l[v];
	tp[2*v+1].first+=l[v];
	tp[2*v+1].second+=l[v];
	l[2*v]+=l[v];
	l[2*v+1]+=l[v];
	l[v]=0;
	return;
}
void dodaj(int v,int a,int b,ll x){
	if(a>p[v].second||b<p[v].first)return;
	if(a<=p[v].first&&b>=p[v].second){
		tp[v].first+=x;
		tp[v].second+=x;
		l[v]+=x;
		return;
	}
	lazy(v);
	dodaj(2*v,a,b,x);
	dodaj(2*v+1,a,b,x);
	tp[v].first=tp[2*v].first;
	tp[v].second=tp[2*v+1].second;
	t[v]=t[2*v]+t[2*v+1];
	if(p[2*v].first==p[2*v].second){
		if(tp[v].first<tp[v].second)bb[v]={0,0};//0 = rosnacy, 1 = malejacy
		else bb[v]={1,1};
		t[v]=max(tp[2*v].second,tp[2*v+1].first)-min(tp[2*v].second,tp[2*v+1].first);
	//	cout<<"pomoc: "<<t[v]<<' '<<bb[v].first<<' '<<bb[v].second<<'\n';
	}
	else{
		bb[v]={bb[2*v].first,bb[2*v+1].second};
		if(tp[2*v].second<tp[2*v+1].first&&bb[2*v].second==0&&bb[2*v+1].first==0)t[v]+=tp[2*v+1].first-tp[2*v].second;
		if(tp[2*v].second>tp[2*v+1].first&&bb[2*v].second==1&&bb[2*v+1].first==1)t[v]+=tp[2*v].second-tp[2*v+1].first;
	}
	return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
	prz(1,0,maxn-1);
	ll n,q,v1,v2,v3,ost;
	cin>>n>>q;
	for(int i=0;i<n;i++){
		cin>>v1;
		ost=v1;
		dodaj(1,i,i,v1);
	}
	dodaj(1,n,maxn-1,ost);
	//cout<<t[1]<<'\n';
	while(q--){
		cin>>v1>>v2>>v3;
		if(v2==n)v2=maxn;
		dodaj(1,v1-1,v2-1,v3);
		cout<<t[1]<<'\n';
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:66:7: warning: 'ost' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |  dodaj(1,n,maxn-1,ost);
      |  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 55.0

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