Submission #158027

#	Time	Username	Problem	Language	Result	Execution time	Memory
158027		ZwariowanyMarcin	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	301 ms	12336 KiB

foehn_phenomena

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;
#define ios cin.tie(0); ios_base::sync_with_stdio(0)	
	
		
using namespace std;	

int n, q;
int a[200000 + 111];
ll res = 0;
int s, t;
int l, r, x;

struct fenwick {
	ll add[200000 + 111];
	
	void init() {
		FOR(i, 1, 200000)
			add[i] = 0;
	}
	
	void dodaj(int x, int c) {
		for(; x <= 200000; x += x & -x) 
			add[x] += c;
	}
	
	ll daj(int x) {
		ll res = 0;
		for(; 0 < x; x -= x & -x)
			res += add[x];
		return res;
	}
	
	ll sum(int id) {
		return daj(200000) - daj(id - 1);
	}
} ja;

void roll(int x) {
	if(x <= 1 || x > n + 1)
		return;
	ll k = abs(ja.sum(x) - ja.sum(x - 1));
	if(ja.sum(x) > ja.sum(x - 1))
		res += (ll) s * k;
	else
		res -= (ll) t * k;
}

void akt(int x) {
	if(x <= 1 || x > n + 1)
		return;
	ll k = abs(ja.sum(x) - ja.sum(x - 1));
	if(ja.sum(x) > ja.sum(x - 1))
		res -= (ll) s * k;
	else
		res += (ll) t * k;
}
					
int main() {	
	ja.init();
	scanf("%d %d %d %d", &n, &q, &s, &t);
	FOR(i, 1, n + 1)
		scanf("%d", &a[i]);
	FOR(i, 2, n + 1) {
		ja.dodaj(i, a[i]);
		ja.dodaj(i - 1, -a[i]);
	}
	FOR(i, 2, n + 1)
		akt(i);
	FOR(i, 1, q) {
		scanf("%d %d %d", &l, &r, &x);
		l += 1;
		r += 1;
		roll(l);
		roll(r + 1);
		ja.dodaj(r, x);
		ja.dodaj(l - 1, -x);
		akt(l);
		akt(r + 1);
		printf("%lld\n", res);
	}
		
		
	
				
	return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &n, &q, &s, &t);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
foehn_phenomena.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &l, &r, &x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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