Submission #203058

#	Time	Username	Problem	Language	Result	Execution time	Memory
203058		blacktulip	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	997 ms	25720 KiB

foehn_phenomena

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo;
typedef pair< lo,lo > PII;
 
#define fi first
#define se second
#define mp make_pair
#define int long long
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;
 
int n,m,b[li],a[li],k,flag,t,ar,az,tree[li*4],lazy[li*4],PS[li],tree1[li*4],lazy1[li*4];
int cev;
string s;
vector<int> v;
 
inline void build(int node,int start,int end){
	if(start>end)return ;
	if(start==end){tree[node]=PS[start];return ;}
	build(node*2,start,mid),build(node*2+1,mid+1,end);
	tree[node]=tree[node*2]+tree[node*2+1];
}
 
inline void update(int node,int start,int end,int l,int r,int val){
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){tree[node]=val;return ;}
	update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
	tree[node]=tree[node*2]+tree[node*2+1];
}
 
inline int query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	if(start>=l && end<=r)return tree[node];
	return query(node*2,start,mid,l,r)+query(node*2+1,mid+1,end,l,r);
}
 
inline void push1(int node,int start,int end){
	if(lazy1[node]==0)return ;
	tree1[node]+=lazy1[node]*(end-start+1);
	if(start!=end){
		lazy1[node*2]+=lazy1[node];
		lazy1[node*2+1]+=lazy1[node];
	}
	lazy1[node]=0;
}
 
inline void build1(int node,int start,int end){
	if(start>end)return ;
	if(start==end){tree1[node]=a[start];return ;}
	build1(node*2,start,mid),build1(node*2+1,mid+1,end);
	tree1[node]=tree1[node*2]+tree1[node*2+1];
}
 
inline void update1(int node,int start,int end,int l,int r,int val){
	
	if(start>end || start>r || end<l)return ;
	push1(node,start,end);
	if(start>=l && end<=r){lazy1[node]+=val;push1(node,start,end);return ;}
	update1(node*2,start,mid,l,r,val),update1(node*2+1,mid+1,end,l,r,val);
	tree1[node]=tree1[node*2]+tree1[node*2+1];
}
 
inline int query1(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	push1(node,start,end);
	if(start>=l && end<=r)return tree1[node];
	return query1(node*2,start,mid,l,r)+query1(node*2+1,mid+1,end,l,r);
}
 
main(void){
	scanf("%lld %lld %lld %lld",&n,&t,&az,&ar);
	////~ scanf("%d",&m);
	for(int i=1;i<=n+1;i++){
		scanf("%lld",&a[i]);
		int at=0;
		if(i==1)continue;
		if(a[i-1]>=a[i])at+=(a[i-1]-a[i])*ar;
		if(a[i-1]<a[i])at-=(a[i]-a[i-1])*az;
		PS[i]=at;
	}
	for(int i=1;i<=n;i++)PS[i]=PS[i+1];
	PS[n+1]=0;
	n++;
	build(1,1,n);
	build1(1,1,n);
	////~ cout<<query(1,1,n,3,4)<<endl;
	while(t--){
		int l,r,x;
		scanf("%lld %lld %lld",&l,&r,&x);
		l++;
		r++;
		cev=query(1,1,n,1,l-2);
		cev+=query(1,1,n,r+1,n);
		cev+=query(1,1,n,l,r-1);
		update1(1,1,n,l,r,x);
		int l1=query1(1,1,n,l-1,l-1);
		int l2=query1(1,1,n,l,l);
		//~ r1=query1(1,1,n,r,r);
		int r2=0,r1=0;
		if(r<n){
			r2=query1(1,1,n,r+1,r+1);
			r1=query1(1,1,n,r,r);
		}
		if(l1>=l2)cev+=(l1-l2)*ar;
		if(l1<l2)cev-=(l2-l1)*az;
		////~ cout<<cev<<endl;
		if(r<n){
			if(r2>r1)cev-=(r2-r1)*az;
			if(r2<=r1)cev+=(r1-r2)*ar;
		}
		if(l1>=l2)update(1,1,n,l-1,l-1,(l1-l2)*ar);
		if(l1<l2)update(1,1,n,l-1,l-1,-(l2-l1)*az);
		if(r<n){
			if(r2>r1)update(1,1,n,r,r,-(r2-r1)*az);
			if(r2<=r1)update(1,1,n,r,r,(r1-r2)*ar);
		}
		
		////~ update(1,1,n,l-1,l-1,x);
		////~ update(1,1,n,r,r,x);
		
		printf("%lld\n",cev);
	}
	return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp:87:10: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(void){
          ^
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld",&n,&t,&az,&ar);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
   ~~~~~^~~~~~~~~~~~~~
foehn_phenomena.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&l,&r,&x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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