oj.uz

Submission #83466

# Submission time Handle Problem Language Result Execution time Memory
83466 2018-11-08T07:13:46 Z ekrem Foehn Phenomena (JOI17_foehn_phenomena) C++
100 / 100
 431 ms 153660 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define N 200005
using namespace std;

typedef long long ll;

ll n, q, s, t, l, r, x, ans, a[N], b[N], seg[4*N];

void bu(ll k, ll bas, ll son){
	if(bas == son){
		seg[k] = a[bas];
		return;
	}
	bu(sol, bas, orta);
	bu(sag, orta + 1, son);
}

ll qu(ll k, ll bas, ll son, ll x){
	if(x == 0)
		return 0;
	if(bas == son)
		return seg[k];
	if(x <= orta)
		return seg[k] + qu(sol, bas, orta, x);
	return seg[k] + qu(sag, orta + 1, son, x);
}

void up(ll k, ll bas, ll son, ll x, ll y, ll z){
	if(bas > y or son < x)
		return;
	if(bas >= x and son <= y){
		seg[k] += z;
		return;
	}
	up(sol, bas, orta, x, y, z);
	up(sag, orta + 1, son, x, y, z);
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%lld %lld %lld %lld",&n ,&q ,&s ,&t);
	for(ll i = 0; i <= n; i++)
		scanf("%lld",a + i);
	for(ll i = 1; i <= n; i++){
		if(a[i] > a[i - 1])
			b[i] = -s * (a[i] - a[i - 1]);
		else
			b[i] = t * (a[i - 1] - a[i]);
		ans += b[i];
	}
	bu(1, 1, n);
	while(q--){
		scanf("%lld %lld %lld",&l ,&r ,&x);
		ans -= b[r + 1] + b[l];
		up(1, 1, n, l, r, x);
		ll a1 = qu(1, 1, n, l - 1);
		ll a2 = qu(1, 1, n, l);
		ll a3 = qu(1, 1, n, r);
		ll a4 = qu(1, 1, n, r + 1);
		if(a2 > a1)
			b[l] = -s * (a2 - a1);
		else
			b[l] = t * (a1 - a2);

		if(a4 > a3)
			b[r + 1] = -s * (a4 - a3);
		else
			b[r + 1] = t * (a3 - a4);
		ans += b[r + 1] + b[l];
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:49:7: 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);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",a + i);
   ~~~~~^~~~~~~~~~~~~~
foehn_phenomena.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&l ,&r ,&x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 5 ms 520 KB Output is correct
3 Correct 7 ms 576 KB Output is correct
4 Correct 7 ms 812 KB Output is correct
5 Correct 5 ms 812 KB Output is correct
6 Correct 7 ms 856 KB Output is correct
7 Correct 4 ms 996 KB Output is correct
8 Correct 5 ms 1040 KB Output is correct
9 Correct 5 ms 1196 KB Output is correct
10 Correct 4 ms 1244 KB Output is correct
11 Correct 4 ms 1308 KB Output is correct
12 Correct 4 ms 1364 KB Output is correct
13 Correct 3 ms 1420 KB Output is correct
14 Correct 3 ms 1464 KB Output is correct
15 Correct 4 ms 1512 KB Output is correct
16 Correct 4 ms 1552 KB Output is correct
17 Correct 3 ms 1600 KB Output is correct
18 Correct 3 ms 1644 KB Output is correct
19 Correct 2 ms 1644 KB Output is correct
20 Correct 2 ms 1644 KB Output is correct
21 Correct 3 ms 1644 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 10228 KB Output is correct
2 Correct 391 ms 10916 KB Output is correct
3 Correct 420 ms 11300 KB Output is correct
4 Correct 359 ms 16164 KB Output is correct
5 Correct 403 ms 23008 KB Output is correct
6 Correct 153 ms 26964 KB Output is correct
7 Correct 186 ms 31632 KB Output is correct
8 Correct 334 ms 38080 KB Output is correct
9 Correct 335 ms 43936 KB Output is correct
10 Correct 335 ms 48180 KB Output is correct
11 Correct 172 ms 52664 KB Output is correct
12 Correct 145 ms 57996 KB Output is correct
13 Correct 184 ms 63060 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 5 ms 520 KB Output is correct
3 Correct 7 ms 576 KB Output is correct
4 Correct 7 ms 812 KB Output is correct
5 Correct 5 ms 812 KB Output is correct
6 Correct 7 ms 856 KB Output is correct
7 Correct 4 ms 996 KB Output is correct
8 Correct 5 ms 1040 KB Output is correct
9 Correct 5 ms 1196 KB Output is correct
10 Correct 4 ms 1244 KB Output is correct
11 Correct 4 ms 1308 KB Output is correct
12 Correct 4 ms 1364 KB Output is correct
13 Correct 3 ms 1420 KB Output is correct
14 Correct 3 ms 1464 KB Output is correct
15 Correct 4 ms 1512 KB Output is correct
16 Correct 4 ms 1552 KB Output is correct
17 Correct 3 ms 1600 KB Output is correct
18 Correct 3 ms 1644 KB Output is correct
19 Correct 2 ms 1644 KB Output is correct
20 Correct 2 ms 1644 KB Output is correct
21 Correct 3 ms 1644 KB Output is correct
22 Correct 378 ms 10228 KB Output is correct
23 Correct 391 ms 10916 KB Output is correct
24 Correct 420 ms 11300 KB Output is correct
25 Correct 359 ms 16164 KB Output is correct
26 Correct 403 ms 23008 KB Output is correct
27 Correct 153 ms 26964 KB Output is correct
28 Correct 186 ms 31632 KB Output is correct
29 Correct 334 ms 38080 KB Output is correct
30 Correct 335 ms 43936 KB Output is correct
31 Correct 335 ms 48180 KB Output is correct
32 Correct 172 ms 52664 KB Output is correct
33 Correct 145 ms 57996 KB Output is correct
34 Correct 184 ms 63060 KB Output is correct
35 Correct 370 ms 67488 KB Output is correct
36 Correct 398 ms 74188 KB Output is correct
37 Correct 407 ms 80344 KB Output is correct
38 Correct 378 ms 85484 KB Output is correct
39 Correct 390 ms 91000 KB Output is correct
40 Correct 381 ms 96372 KB Output is correct
41 Correct 377 ms 101536 KB Output is correct
42 Correct 393 ms 107184 KB Output is correct
43 Correct 393 ms 111868 KB Output is correct
44 Correct 431 ms 116928 KB Output is correct
45 Correct 383 ms 122488 KB Output is correct
46 Correct 395 ms 129168 KB Output is correct
47 Correct 173 ms 131848 KB Output is correct
48 Correct 185 ms 136400 KB Output is correct
49 Correct 363 ms 140964 KB Output is correct
50 Correct 202 ms 145124 KB Output is correct
51 Correct 148 ms 149000 KB Output is correct
52 Correct 207 ms 153660 KB Output is correct