답안 #839091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839091	2023-08-28T15:47:42 Z	fanwen	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	99 ms	9624 KB

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

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, T 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.

Compilation message

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

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	464 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	464 KB	Output is correct
12	Correct	2 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	2 ms	340 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	7244 KB	Output is correct
2	Correct	99 ms	7776 KB	Output is correct
3	Correct	98 ms	8356 KB	Output is correct
4	Correct	81 ms	7504 KB	Output is correct
5	Correct	85 ms	8268 KB	Output is correct
6	Correct	72 ms	8788 KB	Output is correct
7	Correct	74 ms	8660 KB	Output is correct
8	Correct	90 ms	8636 KB	Output is correct
9	Correct	91 ms	9036 KB	Output is correct
10	Correct	89 ms	7716 KB	Output is correct
11	Correct	70 ms	8700 KB	Output is correct
12	Correct	69 ms	9124 KB	Output is correct
13	Correct	72 ms	9548 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	464 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	464 KB	Output is correct
12	Correct	2 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	2 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	2 ms	340 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	92 ms	7244 KB	Output is correct
23	Correct	99 ms	7776 KB	Output is correct
24	Correct	98 ms	8356 KB	Output is correct
25	Correct	81 ms	7504 KB	Output is correct
26	Correct	85 ms	8268 KB	Output is correct
27	Correct	72 ms	8788 KB	Output is correct
28	Correct	74 ms	8660 KB	Output is correct
29	Correct	90 ms	8636 KB	Output is correct
30	Correct	91 ms	9036 KB	Output is correct
31	Correct	89 ms	7716 KB	Output is correct
32	Correct	70 ms	8700 KB	Output is correct
33	Correct	69 ms	9124 KB	Output is correct
34	Correct	72 ms	9548 KB	Output is correct
35	Correct	95 ms	7372 KB	Output is correct
36	Correct	92 ms	8736 KB	Output is correct
37	Correct	97 ms	9564 KB	Output is correct
38	Correct	96 ms	9372 KB	Output is correct
39	Correct	94 ms	9292 KB	Output is correct
40	Correct	95 ms	9292 KB	Output is correct
41	Correct	92 ms	9168 KB	Output is correct
42	Correct	93 ms	9392 KB	Output is correct
43	Correct	92 ms	8520 KB	Output is correct
44	Correct	93 ms	8904 KB	Output is correct
45	Correct	85 ms	8716 KB	Output is correct
46	Correct	90 ms	9420 KB	Output is correct
47	Correct	78 ms	9292 KB	Output is correct
48	Correct	77 ms	9624 KB	Output is correct
49	Correct	77 ms	8544 KB	Output is correct
50	Correct	76 ms	9324 KB	Output is correct
51	Correct	71 ms	9324 KB	Output is correct
52	Correct	70 ms	9292 KB	Output is correct