oj.uz

Submission #99736

# Submission time Handle Problem Language Result Execution time Memory
99736 2019-03-06T11:13:54 Z psmao Foehn Phenomena (JOI17_foehn_phenomena) C++14
100 / 100
 843 ms 23032 KB 
#include <bits/stdc++.h>
using namespace std;

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}

const int maxn = 200050;

int n, q, s, t, a[maxn];
struct node{ll sum, tag; int l, r;}tr[maxn<<2];

void pd(int k)
{
	if(tr[k].tag)
	{
		tr[k<<1].tag += tr[k].tag;
		tr[k<<1|1].tag += tr[k].tag;
		tr[k<<1].sum += tr[k].tag * (tr[k<<1].r - tr[k<<1].l + 1);
		tr[k<<1|1].sum += tr[k].tag * (tr[k<<1|1].r - tr[k<<1|1].l + 1);
		tr[k].tag = 0;
	}
}
void pu(int k)
{
	tr[k].sum = tr[k<<1].sum + tr[k<<1|1].sum;
}
void build(int l, int r, int k = 1)
{
	tr[k].l = l; tr[k].r = r; tr[k].tag = 0;
	if(l == r) {tr[k].sum = a[l]; return;}
	int mid = l + r >> 1;
	build(l, mid, k<<1);
	build(mid+1, r, k<<1|1);
	pu(k);
}
void upd(int l, int r, int x, int k = 1)
{
	if(l <= tr[k].l && tr[k].r <= r) 
	{
		tr[k].sum += x * (tr[k].r - tr[k].l + 1);
		tr[k].tag += x;
		return;
	}
	pd(k);
	int mid = tr[k].l + tr[k].r >> 1;
	if(r <= mid) upd(l, r, x, k<<1);
	else if(l > mid) upd(l, r, x, k<<1|1);
	else upd(l, mid, x, k<<1), upd(mid+1, r, x, k<<1|1);
	pu(k);
}
ll ask(int p, int k = 1)
{
	if(tr[k].l == tr[k].r) return tr[k].sum;
	pd(k);
	int mid = tr[k].l + tr[k].r >> 1;
	if(p <= mid) return ask(p, k<<1);
	else return ask(p, k<<1|1);
}
int main()
{
	#ifdef MPS	
		fp("1.in","r",stdin);
		fp("1.out","w",stdout);
	#endif
	sf("%d%d%d%d",&n,&q,&s,&t);
	s = -s;
	fo(i,0,n) sf("%d",&a[i]);
	ll ans = 0;
	fo(i,0,n-1) 
		if(a[i] < a[i+1]) ans += (a[i+1]-a[i])*1ll*s; 
		else ans += (a[i]-a[i+1])*1ll*t;
	build(0, n);
	fo(i,1,q)
	{
		int l, r, x;
		sf("%d%d%d",&l,&r,&x);
		ll oa = ask(l), ob = ask(r), w;
		w = ask(l-1); ans -= abs(oa - w) * 1ll * (w < oa ? s : t);
		if(r != n)
		{
			w = ask(r+1);
			ans -= abs(ob - w) * 1ll * (ob < w ? s : t);
		}
		upd(l, r, x);
		oa = ask(l); ob = ask(r);
		w = ask(l-1); ans += abs(oa - w) * 1ll * (w < oa ? s : t);
		if(r != n)
		{
			w = ask(r+1);
			ans += abs(ob - w) * 1ll * (ob < w ? s : t);
		}
		pf("%lld\n",ans);
	}
	return 0;
}

Compilation message

foehn_phenomena.cpp: In function 'void build(int, int, int)':
foehn_phenomena.cpp:57:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
foehn_phenomena.cpp: In function 'void upd(int, int, int, int)':
foehn_phenomena.cpp:71:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tr[k].l + tr[k].r >> 1;
            ~~~~~~~~^~~~~~~~~
foehn_phenomena.cpp: In function 'll ask(int, int)':
foehn_phenomena.cpp:81:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tr[k].l + tr[k].r >> 1;
            ~~~~~~~~^~~~~~~~~
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:91:4: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  sf("%d%d%d%d",&n,&q,&s,&t);
    ^
foehn_phenomena.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fo(i,0,n) sf("%d",&a[i]);
              ^
foehn_phenomena.cpp:102:5: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   sf("%d%d%d",&l,&r,&x);
     ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 6 ms 484 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 8 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 7 ms 556 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 9 ms 512 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 20324 KB Output is correct
2 Correct 780 ms 20932 KB Output is correct
3 Correct 828 ms 21412 KB Output is correct
4 Correct 751 ms 21008 KB Output is correct
5 Correct 700 ms 22000 KB Output is correct
6 Correct 418 ms 20984 KB Output is correct
7 Correct 388 ms 20984 KB Output is correct
8 Correct 635 ms 21880 KB Output is correct
9 Correct 644 ms 22136 KB Output is correct
10 Correct 622 ms 20964 KB Output is correct
11 Correct 382 ms 20932 KB Output is correct
12 Correct 429 ms 21652 KB Output is correct
13 Correct 407 ms 21880 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 6 ms 484 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 8 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 7 ms 556 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 5 ms 512 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 6 ms 512 KB Output is correct
18 Correct 9 ms 512 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 843 ms 20324 KB Output is correct
23 Correct 780 ms 20932 KB Output is correct
24 Correct 828 ms 21412 KB Output is correct
25 Correct 751 ms 21008 KB Output is correct
26 Correct 700 ms 22000 KB Output is correct
27 Correct 418 ms 20984 KB Output is correct
28 Correct 388 ms 20984 KB Output is correct
29 Correct 635 ms 21880 KB Output is correct
30 Correct 644 ms 22136 KB Output is correct
31 Correct 622 ms 20964 KB Output is correct
32 Correct 382 ms 20932 KB Output is correct
33 Correct 429 ms 21652 KB Output is correct
34 Correct 407 ms 21880 KB Output is correct
35 Correct 711 ms 20592 KB Output is correct
36 Correct 644 ms 21880 KB Output is correct
37 Correct 680 ms 22652 KB Output is correct
38 Correct 685 ms 22520 KB Output is correct
39 Correct 706 ms 22564 KB Output is correct
40 Correct 686 ms 22432 KB Output is correct
41 Correct 623 ms 22392 KB Output is correct
42 Correct 631 ms 22544 KB Output is correct
43 Correct 667 ms 21624 KB Output is correct
44 Correct 733 ms 21948 KB Output is correct
45 Correct 642 ms 22028 KB Output is correct
46 Correct 681 ms 23032 KB Output is correct
47 Correct 404 ms 21700 KB Output is correct
48 Correct 320 ms 21624 KB Output is correct
49 Correct 688 ms 20668 KB Output is correct
50 Correct 373 ms 21608 KB Output is correct
51 Correct 354 ms 21880 KB Output is correct
52 Correct 462 ms 21700 KB Output is correct