제출 #839090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839090		fanwen	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	109 ms	16224 KiB

foehn_phenomena

/**
 *      author : pham van sam 
 *      created : 28 August 2023 (Monday)
 **/

#include <bits/stdc++.h>

#ifdef LOCAL
	#include "debug.h"
#else 
	#define debug(...) 30
	#define clog if(false) cerr
#endif // LOCAL

#define int long long

using namespace std;

template < class T, T (*f) (T, T), T (*e) ()>
struct segment_tree {
    vector <T> tree;
    int n;

    void update(int u, int p) {
        u--;
        for(tree[u += n] += p; u >>= 1; ) {
            tree[u] = f(tree[u << 1], tree[u << 1 | 1]);
        }
    }

    void set(int u, int p) {
        u--;
        for (tree[u += n] = p; u >>= 1; ) {
            tree[u] = f(tree[u << 1], tree[u << 1 | 1]);
        }
    }

    T get(int p) {
        return tree[p += n - 1];
    }

    T get(int l, int r) {
        l--;
        T resl = e(), resr = e();
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) resl = f(resl, tree[l++]);
            if(r & 1) resr = f(tree[--r], resr);
        }
        return f(resl, resr);
    }

    segment_tree(int n = 0) : n(n), tree(n << 1 | 1) {
        fill(tree.begin(), tree.end(), 0);
    }
};

long long _sum_(long long a, long long b) { return a + b; }
long long e() { return 0LL; }

const int MAXN = 2e5 + 5;

int S, T, n, q, a[MAXN];
long long diff[MAXN];

void you_make_it(void) {
	cin >> n >> q >> S >> T;
	for (int i = 0; i <= n; ++i) {
		cin >> a[i];
		if(i > 0) diff[i] = a[i] - a[i - 1];
	}
	long long sum_neg = 0;
	segment_tree <long long, _sum_, e> it(n);
	for (int i = 1; i <= n; ++i) {
		if(diff[i] <= 0) sum_neg -= diff[i];
		else it.set(i, diff[i]);
	}

	auto update = [&](int i, int w) {
		if(i > n) return;
		if(diff[i] <= 0) {
			if(diff[i] + w > 0) {
				sum_neg += diff[i];
				it.set(i, diff[i] += w);
			} else {
				sum_neg += diff[i];
				sum_neg -= (diff[i] += w);
			}
		} else {
			if(diff[i] + w <= 0) {
				it.set(i, 0);
				diff[i] += w;
				sum_neg -= diff[i];
			} else {
				diff[i] += w;
				it.set(i, diff[i]);
			}
		}
	};
	for (int i = 1; i <= n; ++i) clog << a[i] << " \n"[i == n];
	for (int i = 1; i <= n; ++i) clog << diff[i] << " \n"[i == n];
	clog << debug(sum_neg) << '\n';
	while(q--) {
		int l, r, w; cin >> l >> r >> w;
		update(l, w); update(r + 1, -w);
		cout << - 1LL * it.get(1, n) * S + 1LL * sum_neg * T << '\n';
		clog << debug(sum_neg) << '\n'; 
	}
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

컴파일 시 표준 에러 (stderr) 메시지

foehn_phenomena.cpp: In instantiation of 'segment_tree<T, f, e>::segment_tree(long long int) [with T = long long int; T (* f)(T, T) = _sum_; T (* e)() = e]':
foehn_phenomena.cpp:72:41:   required from here
foehn_phenomena.cpp:22:9: warning: 'segment_tree<long long int, _sum_, e>::n' will be initialized after [-Wreorder]
   22 |     int n;
      |         ^
foehn_phenomena.cpp:21:16: warning:   'std::vector<long long int, std::allocator<long long int> > segment_tree<long long int, _sum_, e>::tree' [-Wreorder]
   21 |     vector <T> tree;
      |                ^~~~
foehn_phenomena.cpp:52:5: warning:   when initialized here [-Wreorder]
   52 |     segment_tree(int n = 0) : n(n), tree(n << 1 | 1) {
      |     ^~~~~~~~~~~~

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