Submission #156455

#	Time	Username	Problem	Language	Result	Execution time	Memory
156455		wilwxk	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	572 ms	27372 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node {
	ll lv, rv, lz, v;
};

const int MAXN=2e5+3;
int v[MAXN];
node seg[MAXN*4];
int n, q, x, y;

void remerge(int sind, int e, int d) {
	seg[sind].v=seg[e].v+seg[d].v;
	ll val=seg[d].lv-seg[e].rv;
	seg[sind].v+= val<0 ? -val*(ll)y : -val*(ll)x;
	seg[sind].lv=seg[e].lv;
	seg[sind].rv=seg[d].rv;
}	

void build(int sind, int ini, int fim) {
	if(ini==fim) {
		seg[sind].rv=seg[sind].lv=v[ini];
		seg[sind].lz=0;
		return;
	}
	int mid=(ini+fim)/2;
	int e=sind*2; int d=e+1;
	build(e, ini, mid);
	build(d, mid+1, fim);
	remerge(sind, e, d);
}

void refresh(int sind, int ini, int fim) {
	if(!seg[sind].lz) return;
	seg[sind].lv+=seg[sind].lz;
	seg[sind].rv+=seg[sind].lz;
	if(ini==fim) {
		seg[sind].lz=0;
		return;
	}
	int e=sind*2; int d=e+1;
	seg[e].lz+=seg[sind].lz;
	seg[d].lz+=seg[sind].lz;
	seg[sind].lz=0;
	return;
}

void update(int sind, int ini, int fim, int qini, int qfim, int val) {
	refresh(sind, ini, fim);
	if(qfim<ini||qini>fim) return;
	if(qini<=ini&&qfim>=fim) {
		seg[sind].lz=val;
		refresh(sind, ini, fim);
		return;
	}
	int mid=(ini+fim)/2;
	int e=sind*2; int d=e+1;
	update(e, ini, mid, qini, qfim, val);
	update(d, mid+1, fim, qini, qfim, val);
	remerge(sind, e, d);
}

int main() {
	scanf("%d %d %d %d", &n, &q, &x, &y); n++;
	for(int i=1; i<=n; i++) scanf("%d", &v[i]);
	build(1, 1, n);

	while(q--) {
		int ini, fim, val;
		scanf("%d %d %d", &ini, &fim, &val);
		update(1, 1, n, ini+1, fim+1, val);
		printf("%lld\n", seg[1].v);
	}


}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:66: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, &x, &y); n++;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:67:31: 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("%d", &v[i]);
                          ~~~~~^~~~~~~~~~~~~
foehn_phenomena.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &ini, &fim, &val);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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