Submission #670449

#	Time	Username	Problem	Language	Result	Execution time	Memory
670449		radal	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	382 ms	8952 KiB

foehn_phenomena

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
constexpr int N = 2e5+10,mod = 1e9+7,maxm = 210;
constexpr ll inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
   // if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
 

ll seg[N*4];
int a[N];

void upd(int l,int r,int s,int e,int x,int v = 1){
	if (s <= l && r <= e){
		seg[v] += x;
		return;
	}
	if (s >= r || l >= e) return;
	int m = (l+r) >> 1,u = (v << 1);
	upd(l,m,s,e,x,u);
	upd(m,r,s,e,x,u|1);
}

ll que(int l,int r,int p,int v = 1){
	if (r-l == 1) return seg[v];
	int m = (l+r) >> 1,u = (v << 1);
	if (p < m) return que(l,m,p,u)+seg[v];
	return que(m,r,p,u|1)+seg[v];
}

int main(){
	ios :: sync_with_stdio(0); cin.tie(0); 
	int n,q,s,t;
	cin >> n >> q >> s >> t;
	ll cnt1 = 0,cnt2 = 0;
	s *= -1;
	rep(i,0,n+1){
	   	cin >> a[i];
		if (i && a[i] > a[i-1]) cnt1 += a[i]-a[i-1];
		else if (i) cnt2 += a[i-1]-a[i];
		upd(0,n+1,i,i+1,a[i]);
	}
	while (q--){
		int l,r,h;
		cin >> l >> r >> h;
		ll x = que(0,n+1,l),y = que(0,n+1,l-1);
		if (x > y) cnt1 -= (x-y);
		else cnt2 -= (y-x);
		if (r < n){
			x = que(0,n+1,r),y = que(0,n+1,r+1);
			if (x < y) cnt1 -= (y-x);
			else cnt2 -= (x-y);
		}
		upd(0,n+1,l,r+1,h);
        x = que(0,n+1,l),y = que(0,n+1,l-1);
        if (x > y) cnt1 += (x-y);
        else cnt2 += (y-x);
        if (r < n){
            x = que(0,n+1,r),y = que(0,n+1,r+1);
            if (x < y) cnt1 += (y-x);
            else cnt2 += (x-y);
        }  
		cout << 1ll*cnt1*s+1ll*cnt2*t << endl;
	}
}

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