Submission #875592

#	Time	Username	Problem	Language	Result	Execution time	Memory
875592		ReLice	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	10 / 100	374 ms	23732 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define ins insert
#define bc back()
#define str string
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18+7;
const ll mod=1e9;
const ll N=2e5+7;
const ld eps=1e-9;

vector<ll> t(N*4);
ll add[N*4],a[N],vv[N];
void build(ll v,ll tl,ll tr){
	if(tl==tr){
		t[v]=vv[tl];
		return;
	}
	ll tm=(tl+tr)/2;
	build(v*2,tl,tm);
	build(v*2+1,tm+1,tr);
}
void push(ll v,ll tl,ll tr){
	if(tl!=tr){
		add[v*2]+=add[v];
		add[v*2+1]+=add[v];
	}
	else t[v]+=add[v];
	add[v]=0;
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll val){
	push(v,tl,tr);
	if(tl>r || tr<l) return;
	if(l<=tl && tr<=r){
		add[v]+=val;
		push(v,tl,tr);
		return;
	}
	ll tm=(tl+tr)/2;
	upd(v*2,tl,tm,l,r,val);
	upd(v*2+1,tm+1,tr,l,r,val);
}
ll get(ll v,ll tl,ll tr,ll pos){
	push(v,tl,tr);
	if(tl>pos || tr<pos)return 0ll;
	if(tl==tr){
		return t[v];
	}
	ll tm=(tl+tr)/2;
	return max(get(v*2,tl,tm,pos),get(v*2+1,tm+1,tr,pos));
}
void solve(){
    ll i,j;
    ll n,q,x,y;
    cin>>n>>q>>x>>y;
    for(i=1;i<=n+1;i++){
		cin>>vv[i];
		if(i>1){
			a[i]=a[i-1]+(vv[i-1]-vv[i]<0 ? (vv[i-1]-vv[i])*x : (vv[i-1]-vv[i])*y);
		}
	}
	build(1,1,n+1);
	ll sum=a[n+1];
	ll l,r,b;
	n++;
	for(i=0;i<q;i++){
		cin>>l>>r>>b;
		if(r+1==n){
			ll l1=get(1,1,n,l),l2=get(1,1,n,l+1);
			ll prev=l1-l2,cur=l1-(l2+b);
			sum-=(prev<0 ? prev*x : prev*y);
			sum+=(cur<0 ? cur*x : cur*y);
			upd(1,1,n,l+1,r+1,b);
		}else{
			ll l1=get(1,1,n,l),l2=get(1,1,n,l+1),r1=get(1,1,n,r+1),r2=get(1,1,n,r+2);
			ll prev=l1-l2,cur=l1-(l2+b);
			sum-=(prev<0 ? prev*x : prev*y);
			sum+=(cur<0 ? cur*x : cur*y);
			prev=r1-r2,cur=(r1+b)-r2;
			sum-=(prev<0 ? prev*x : prev*y);
			sum+=(cur<0 ? cur*x : cur*y);
			upd(1,1,n,l+1,r+1,b);
		}
		cout<<sum<<endl;
	}
		
		
}

signed main(){
    start();
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll t=1;
    //cin>>t;
    while(t--) solve();
}
/*









*/

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void solve()':
foehn_phenomena.cpp:71:10: warning: unused variable 'j' [-Wunused-variable]
   71 |     ll i,j;
      |          ^
foehn_phenomena.cpp: In function 'void fre(std::string)':
foehn_phenomena.cpp:19:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:19:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 10 / 10
• Subtask 3: 0 / 60