Submission #33262

#	Time	Username	Problem	Language	Result	Execution time	Memory
33262		UncleGrandpa925	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	30 / 100	246 ms	5140 KiB

foehn_phenomena

/*input
3 5 1 2
0 4 1 8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5

2 2 5 5
0 6 -1
1 1 4
1 2 8


*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 200005
#define bit(x,y) ((x>>y)&1LL)
#define show(x) cout << (#x) << ": " << x << endl;
#define ii pair<int,int>
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}

int n, q, S, T;
int a[N];

class BITrangeSum {
private:
	int tree[N];
public:
	void update(int i, int val) {
		for (; i <= N - 5; i += i & -i) tree[i] += val;
		return;
	}
	int get(int i) {
		int ret = 0;
		for (; i; i -= i & -i) ret += tree[i];
		return ret;
	}
	int getTree(int pos) {
		return get(pos) - get(pos - 1);
	}
} BIT;

int acc(int p) {
	return a[p] + BIT.get(p);
}

int curans = 0;
signed main() {
	scanf("%lld %lld %lld %lld", &n, &q, &S, &T); n++;
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	for (int i = 2; i <= n; i++) {
		if (a[i - 1] < a[i]) curans -= S * abs(a[i] - a[i - 1]);
		else curans += T * abs(a[i] - a[i - 1]);
	}
	for (int i = 1; i <= q; i++) {
		int l, r, val;
		scanf("%lld %lld %lld", &l, &r, &val);
		l++; r++;
		if (l != 1) {
			int x = acc(l - 1); int y = acc(l);
			if (x < y) curans += S * abs(x - y);
			else curans -= T * abs(x - y);
		}
		if (r != n) {
			int x = acc(r); int y = acc(r + 1);
			if (x < y) curans += S * abs(x - y);
			else curans -= T * abs(x - y);
		}
		BIT.update(l, val); BIT.update(r + 1, -val);
		if (l != 1) {
			int x = acc(l - 1); int y = acc(l);
			if (x < y) curans -= S * abs(x - y);
			else curans += T * abs(x - y);
		}
		if (r != n) {
			int x = acc(r); int y = acc(r + 1);
			if (x < y) curans -= S * abs(x - y);
			else curans += T * abs(x - y);
		}
		printf("%lld\n", curans);

	}
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
foehn_phenomena.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
foehn_phenomena.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
foehn_phenomena.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:89:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld", &n, &q, &S, &T); n++;
                                              ^
foehn_phenomena.cpp:90:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
                                                   ^
foehn_phenomena.cpp:97:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld", &l, &r, &val);
                                        ^

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