Submission #516335

#	Time	Username	Problem	Language	Result	Execution time	Memory
516335		DeMen100ns	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	683 ms	11460 KiB

foehn_phenomena

/*
Author : DeMen100ns (a.k.a Vo Khac Trieu self-destruct)
School : VNU-HCM High school for the Gifted
*/

#include <bits/stdc++.h>

#define int long long

using namespace std;

template<typename T> int SIZE(T (&t)){ return t.size(); } template<typename T, size_t N> int SIZE(T (&t)[N]){ return N; } string to_string(char t){ return "'" + string({t}) + "'"; } string to_string(bool t){ return t ? "true" : "false"; } string to_string(const string &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += t[i]; } return '"' + ret + '"'; } string to_string(const char* t){ string ret(t); return to_string(ret); } template<size_t N> string to_string(const bitset<N> &t, int x1=0, int x2=1e9){ string ret = ""; for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){ ret += t[i] + '0'; } return to_string(ret); } template<typename T, typename... Coords> string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C); template<typename T, typename S> string to_string(const pair<T, S> &t){ return "(" + to_string(t.first) + ", " + to_string(t.second) + ")"; } template<typename T, typename... Coords> string to_string(const T (&t), int x1, int x2, Coords... C){ string ret = "["; x1 = min(x1, SIZE(t)); auto e = begin(t); advance(e,x1); for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){ ret += to_string(*e, C...) + (i != _i ? ", " : ""); e = next(e); } return ret + "]"; } template<int Index, typename... Ts> struct print_tuple{ string operator() (const tuple<Ts...>& t) { string ret = print_tuple<Index - 1, Ts...>{}(t); ret += (Index ? ", " : ""); return ret + to_string(get<Index>(t)); } }; template<typename... Ts> struct print_tuple<0, Ts...> { string operator() (const tuple<Ts...>& t) { return to_string(get<0>(t)); } }; template<typename... Ts> string to_string(const tuple<Ts...>& t) { const auto Size = tuple_size<tuple<Ts...>>::value; return print_tuple<Size - 1, Ts...>{}(t); } void dbgr(){;} template<typename Heads, typename... Tails> void dbgr(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgr(T...); } void dbgs(){;} template<typename Heads, typename... Tails> void dbgs(Heads H, Tails... T){ cout << H << " "; dbgs(T...); } 
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

const int N = 2e5 + 5;
const long long INF = 1e18 + 7;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;

int a[N], seg[4 * N], lazy[4 * N];
int n, s, t;

void down(int id){
	int t = lazy[id];
	seg[id << 1] += t;
	seg[id << 1 | 1] += t;
	lazy[id << 1] += t;
	lazy[id << 1 | 1] += t;
	lazy[id] = 0;
}

void upd(int id, int l, int r, int u, int v, int val){
	if (l > v || r < u) return;
	if (l >= u && r <= v){
		seg[id] += val;
		lazy[id] += val;
		return;
	}
	down(id);
	int mid = (l + r) >> 1;
	upd(id << 1, l, mid, u, v, val);
	upd(id << 1 | 1, mid + 1, r, u, v, val);
}

int get(int id, int l, int r, int pos){
	if (l == r) return seg[id];
	down(id);
	int mid = (l + r) >> 1;
	if (mid >= pos) return get(id << 1, l, mid, pos);
	else return get(id << 1 | 1, mid + 1, r, pos);
}

int get_ans(int p){
	if (p > n) return 0;
	int v2 = get(1, 1, n, p);
	int v1 = 0;
	if (p > 1) v1 = get(1, 1, n, p - 1);
	//dbgm(v1, v2);
	if (v2 > v1) return -s * (v2 - v1);
	else return t * (v1 - v2);
}

void solve(){
    int q, ans = 0;
    cin >> n >> q >> s >> t;
    for(int i = 0; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i){
    	if (a[i] > a[i - 1]) ans -= s * (a[i] - a[i - 1]);
    	else ans += t * (a[i - 1] - a[i]);
    }	
    cout << ans << endl;
    for(int i = 1; i <= n; ++i) upd(1, 1, n, i, i, a[i]);
    while (q--){
    	int l, r, v;
    	cin >> l >> r >> v;
    	ans -= get_ans(l);
    	ans -= get_ans(r + 1);
    	upd(1, 1, n, l, r, v);
    	ans += get_ans(l);
    	ans += get_ans(r + 1);
    	cout << ans << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    //freopen("codeforces.inp","r",stdin);
    //freopen("codeforces.out","w",stdout);
    
    int t = 1; //cin >> t;
    while(t--){
        solve();
    }
}

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