Submission #561847

#	Time	Username	Problem	Language	Result	Execution time	Memory
561847		dattranxxx	Foehn Phenomena (JOI17_foehn_phenomena)	C++11	100 / 100	451 ms	42104 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void file() {
	const string FILE_NAME = "FILE_NAME";
	freopen((FILE_NAME + ".inp").c_str(), "r", stdin);
	freopen((FILE_NAME + ".out").c_str(), "w", stdout);
}
const int N = 2e5 + 5; 
int a[N];
int n, q, S, T;
struct V {
	int greater = 0, equal_or_less = 0;
	ll first = 0, last = 0;
	ll res = 0, lazy = 0;
	void add(ll v) {
		lazy += v, first += v, last += v;
	}
};
V merge(V& x, V& y) {
	V z;
	z.first = x.first, z.last = y.last;
	z.res = x.res + y.res, 
	z.greater = x.greater + y.greater, 
	z.equal_or_less = x.equal_or_less + y.equal_or_less;
	if (y.first > x.last) z.res -= S * (y.first - x.last), z.greater++;
	else z.res += T * (x.last - y.first), z.equal_or_less++;
	return z;
}
struct segment_tree {
	vector<V> st;
	int n, x, y, v;
	segment_tree(int n): n(n), st((n + 1) << 2) {
		build(1, 0, n);
	}
	void push(int k) {
		st[k << 1].add(st[k].lazy);
		st[k << 1 | 1].add(st[k].lazy);
		st[k].lazy = 0;
	}
	void build(int k, int l, int r) {
		if (l == r) 
			return st[k].first = st[k].last = a[l], void();
		int m = (l + r) >> 1;
		build(k << 1, l, m);
		build(k << 1 | 1, m+1, r);
		st[k] = merge(st[k << 1], st[k << 1 | 1]);
	}
	void add(int k, int l, int r) {
		if (l > y || r < x) return;
		if (l >= x && r <= y) 
			return st[k].add(v), void();
		int m = (l + r) >> 1;
		push(k);
		add(k << 1, l, m);
		add(k << 1 | 1, m+1, r);
		st[k] = merge(st[k << 1], st[k << 1 | 1]);
		// cerr << ' '<< l << ' ' << r << ' ' << st[k].first << ' ' << st[k].last << ' ' << st[k].greater << ' ' << st[k].equal_or_less << ' ' << st[k].res << '\n';
	}
	ll get(int l, int r, int val) {
		x = l, y = r, v = val;
		add(1, 0, n);
		return st[1].res;
	}
};
int main() {
	cin.tie(0)->sync_with_stdio(0); cout.tie(0);
	cin >> n >> q >> S >> T;
	for (int i = 0; i <= n; ++i)
		cin >> a[i];
	segment_tree st(n);
	for (int i = 0, l, r, v; i < q; ++i) {
		cin >> l >> r >> v;
		cout << st.get(l, r, v) << '\n';
	}
	return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In constructor 'segment_tree::segment_tree(int)':
foehn_phenomena.cpp:32:6: warning: 'segment_tree::n' will be initialized after [-Wreorder]
   32 |  int n, x, y, v;
      |      ^
foehn_phenomena.cpp:31:12: warning:   'std::vector<V> segment_tree::st' [-Wreorder]
   31 |  vector<V> st;
      |            ^~
foehn_phenomena.cpp:33:2: warning:   when initialized here [-Wreorder]
   33 |  segment_tree(int n): n(n), st((n + 1) << 2) {
      |  ^~~~~~~~~~~~
foehn_phenomena.cpp: In function 'void file()':
foehn_phenomena.cpp:6:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |  freopen((FILE_NAME + ".inp").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:7:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  freopen((FILE_NAME + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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