Submission #1115928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115928		RSAMSD	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	453 ms	41080 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;
int t = 0;
int const f = 2e5 + 10;
long long mod = 1e9 + 7;//998244353;
long long A[f];
int dp1[f];
int dp2[500000+10];
int fact[500000+10];
vector<int> prime;
vector<int> ds[500000+10];
int inds[f];
vector<int> dsu[f];
int par[f];
struct node {
	long long val = 0;
	long long lazy = 0;
};
node segtree[8*f];
struct trpel{
	long long v,u,bank =0;
};
bool B[f];
void redany() {
	ifstream fin;
	ofstream fout;
	fin.open("input.txt");
	fout.open("output.txt");
}
long long powmod(long long a, long long p, long long modd) {
	long long ans = 1;
	while (p > 0) {
		if (p % 2 == 1) {
			ans *= a;
			ans %= modd;
			p--;
		}
		if (p == 0)break;
		a *= a;
		a %= modd;
		p /= 2;
	}
	return ans;
}
void dolazy(int v, int l , int r){
	int mid = (l+r)/2;
	long long cnt = segtree[v].lazy;
	segtree[2*v].lazy+=cnt;
	segtree[2*v+1].lazy+=cnt;
	segtree[2*v].val+=cnt*(mid-l+1);
	segtree[2*v+1].val+=cnt*(r-mid);
	segtree[v].lazy = 0;
}
void build(int v , int l , int r){
	if(l==r){
		segtree[v].val = A[r];
		return;
	}
	int mid = (r+l)/2;
	build(2*v,l, mid);
	build(2*v+1,mid+1,r);
	segtree[v].val = segtree[2*v].val+segtree[2*v+1].val;
}
void upd(int v, int tl, int tr, int l , int r, int val){
	if(tr<l||tl>r)return;
	if(tr<=r&&tl>=l){
		segtree[v].val+=val;
		segtree[v].lazy+=val;
		return;
	}
	dolazy(v,tl,tr);
	int mid = (tl+tr)/2;
	upd(2*v,tl,mid,l,r,val);
	upd(2*v+1,mid+1,tr,l,r,val);
	segtree[v].val = segtree[2*v].val+segtree[2*v+1].val;
}
long long q(int v, int tl, int tr, int pos){
	if(tl==tr&&tr==pos){
		return segtree[v].val;
	}
	dolazy(v, tl, tr);
	int mid = (tl+tr)/2;
	if(pos>mid){
		return q(2*v+1,mid+1,tr,pos);
	}
	else{
		return q(2*v,tl,mid,pos);
	}
}
long long comb(long long n, long long k){
	return ((fact[n]*powmod(fact[k],mod-2,mod))%mod*powmod(fact[n-k],mod-2,mod))%mod;
}
int main() {
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	//cin >> t;
	t = 1;
	for (int hhh = 1;hhh <= t;hhh++) {
		long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
		string s1;
		string s3;
		char s2;
		long long dec = 1;
		bool c = 1;
		priority_queue<pair<long long, long long>> qq;
		queue<int> pp;
		map<pair<int,pair<int,int>>, long long> conv;
		vector<long long> vec;
		cin >> n>>m>>k>>d;
		for(int i =0;i<n+1;i++){
			cin>>A[i];
		}
		build(1,0,n);
		for(int i =0;i<n;i++){
			if(A[i+1]>A[i]){
				mx-=(A[i+1]-A[i])*k;
				B[i] =1;
			}
			else{
				mx+=(A[i]-A[i+1])*d;
				B[i] =0;
			}
		}
		//cout<<mx<<'\n';
		for(int i =0;i<m;i++){
			cin>>l>>r>>k2;
			ll = q(1,0,n,l-1);
			lll = q(1,0,n,l);
			//cout<<ll<<" "<<lll<<'\n';
			if(lll>ll){
				mx+=(lll-ll)*k;
			//	cout<<"added "<<(lll-ll)*k<<'\n';
			}
			else{
				mx-=(ll-lll)*d;
			//	cout<<"losed "<<(lll-ll)*d<<'\n';
			}
			if(r!=n){
				ll = q(1,0,n,r);
				lll = q(1,0,n,r+1);
			//	cout<<"2 :"<<ll<<" "<<lll<<'\n';
				if(lll>ll){
					mx+=(lll-ll)*k;
					//cout<<"added "<<(lll-ll)*k<<'\n';
				}
				else{
					mx-=(ll-lll)*d;
					//cout<<"losed "<<(lll-ll)*d<<'\n';
				}
			}
			upd(1,0,n,l,r,k2);
			ll = q(1,0,n,l-1);
			lll = q(1,0,n,l);
			//cout<<":: "<<ll<<" "<<lll<<'\n';
			if(lll>ll){
				mx-=(lll-ll)*k;
			//	cout<<"losed 2 "<<(lll-ll)*k<<'\n';
			}
			else{
				mx+=(ll-lll)*d;
			//	cout<<"added 2 "<<(lll-ll)*d<<'\n';
			}
			if(r!=n){
				ll = q(1,0,n,r);
				lll = q(1,0,n,r+1);
			//	cout<<":: 2 :"<<ll<<" "<<lll<<'\n';
				if(lll>ll){
					mx-=(lll-ll)*k;
				//	cout<<"losed 2 "<<(lll-ll)*k<<'\n';
				}
				else{
					mx+=(ll-lll)*d;
				//	cout<<"added 2 "<<(lll-ll)*d<<'\n';
				}
			}
			cout<<mx<<'\n';
		}
	}
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:99:60: warning: unused variable 'rr' [-Wunused-variable]
   99 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                            ^~
foehn_phenomena.cpp:99:92: warning: unused variable 'rrr' [-Wunused-variable]
   99 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                            ^~~
foehn_phenomena.cpp:99:101: warning: unused variable 'inf' [-Wunused-variable]
   99 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                                     ^~~
foehn_phenomena.cpp:102:8: warning: unused variable 's2' [-Wunused-variable]
  102 |   char s2;
      |        ^~
foehn_phenomena.cpp:103:13: warning: unused variable 'dec' [-Wunused-variable]
  103 |   long long dec = 1;
      |             ^~~
foehn_phenomena.cpp:104:8: warning: unused variable 'c' [-Wunused-variable]
  104 |   bool c = 1;
      |        ^

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