Submission #205673

#	Time	Username	Problem	Language	Result	Execution time	Memory
205673		T0p_	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	486 ms	32120 KiB

foehn_phenomena

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

struct tree
{
	long long lh, rh, laz, s, t;
};

long long arr[200200];
tree seg[800800];

void build(int l, int r, int idx)
{
	if(l == r) return void(seg[idx] = {arr[l], arr[l], 0, 0, 0});
	int mid = (l+r)>>1;
	build(l, mid, idx<<1);
	build(mid+1, r, idx<<1|1);
	long long lh = seg[idx<<1].lh;
	long long rh = seg[idx<<1|1].rh;
	long long laz = 0;
	long long s = seg[idx<<1].s + seg[idx<<1|1].s;
	long long t = seg[idx<<1].t + seg[idx<<1|1].t;
	if(seg[idx<<1].rh < seg[idx<<1|1].lh) s += seg[idx<<1|1].lh - seg[idx<<1].rh;
	else t += seg[idx<<1].rh - seg[idx<<1|1].lh;
	seg[idx] = {lh, rh, laz, s, t};
}

void push_lazy(int l, int r, int idx)
{
	if(seg[idx].laz)
	{
		seg[idx].lh += seg[idx].laz;
		seg[idx].rh += seg[idx].laz;
		if(l != r)
		{
			seg[idx<<1].laz += seg[idx].laz;
			seg[idx<<1|1].laz += seg[idx].laz;
		}
		seg[idx].laz = 0;
	}
}

void update(int l, int r, int idx, int a, int b, int v)
{
	push_lazy(l, r, idx);
	if(r < a || b < l) return ;
	if(a <= l && r <= b)
	{
		seg[idx].lh += v;
		seg[idx].rh += v;
		if(l!=r)
		{
			seg[idx<<1].laz += v;
			seg[idx<<1|1].laz += v;
		}
		return ;
	}
	int mid = (l+r)>>1;
	update(l, mid, idx<<1, a, b, v);
	update(mid+1, r, idx<<1|1, a, b, v);
	long long lh = seg[idx<<1].lh;
	long long rh = seg[idx<<1|1].rh;
	long long laz = 0;
	long long s = seg[idx<<1].s + seg[idx<<1|1].s;
	long long t = seg[idx<<1].t + seg[idx<<1|1].t;
	if(seg[idx<<1].rh < seg[idx<<1|1].lh) s += seg[idx<<1|1].lh - seg[idx<<1].rh;
	else t += seg[idx<<1].rh - seg[idx<<1|1].lh;
	seg[idx] = {lh, rh, laz, s, t};
}

int main()
{
	int n, q, s, t;
	scanf(" %d %d %d %d",&n,&q,&s,&t);
	for(int i=0 ; i<=n ; i++)
		scanf(" %lld",&arr[i]);
	build(0, n, 1);
	while(q--)
	{
		long long l, r, k;
		scanf(" %d %d %d",&l,&r,&k);
		update(0, n, 1, l, r, k);
		printf("%lld\n",seg[1].t * t - seg[1].s * s);
	}
	return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:81:29: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf(" %d %d %d",&l,&r,&k);
                     ~~      ^
foehn_phenomena.cpp:81:29: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
foehn_phenomena.cpp:81:29: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
foehn_phenomena.cpp:74: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:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %lld",&arr[i]);
   ~~~~~^~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d %d %d",&l,&r,&k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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