oj.uz

Submission #74565

# Submission time Handle Problem Language Result Execution time Memory
74565 2018-09-03T18:43:21 Z shoemakerjo Foehn Phenomena (JOI17_foehn_phenomena) C++14
100 / 100
 299 ms 167452 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define maxn 200010

int N, Q;
ll S, T;

ll A[maxn];
ll BIT[maxn]; //store offsets

void up(int spot, ll diff) {
	while (spot < maxn) {
		BIT[spot] += diff;
		spot += spot & (-spot);
	}
}

void update(int l, int r, ll diff) {
	l+=2;
	r+=2;
	up(l, diff);
	up(r+1, 0-diff);
}

ll query(int spot) {
	spot+=2;
	ll res = 0LL;
	while (spot > 0) {
		res += BIT[spot];
		spot -= spot & (-spot);
	}
	return res;
}

ll getval(int spot) {
	return A[spot] + query(spot); //think this is good
}

ll docons(ll v1, ll v2) {
	if (v1 < v2) {
		return -1LL*S*(v2-v1);
	}
	return T*(v1-v2);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> Q >> S >> T;
	for (int i = 0; i <= N; i++) {
		cin >> A[i];
	}
	ll cans = 0LL;
	for (int i = 1; i <= N; i++) {
		cans += docons(A[i-1], A[i]);
	}
	int l, r;
	ll x;
	while (Q--) {
		cin >> l >> r >> x;
		ll odiff = 0LL;
		ll v1, v2;
		if (l != 0) {
			odiff += docons(getval(l-1), getval(l));
		}
		if (r != N) {
			odiff += docons(getval(r), getval(r+1));
		}
		cans -= odiff;
		update(l, r, x);
		if (l != 0) cans += docons(getval(l-1), getval(l));
		if (r != N) cans += docons(getval(r), getval(r+1));

		cout << cans << '\n';
	}	
	cout.flush();

}

Compilation message

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:64:6: warning: unused variable 'v1' [-Wunused-variable]
   ll v1, v2;
      ^~
foehn_phenomena.cpp:64:10: warning: unused variable 'v2' [-Wunused-variable]
   ll v1, v2;
          ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 4 ms 700 KB Output is correct
3 Correct 4 ms 704 KB Output is correct
4 Correct 5 ms 812 KB Output is correct
5 Correct 4 ms 952 KB Output is correct
6 Correct 5 ms 952 KB Output is correct
7 Correct 4 ms 1116 KB Output is correct
8 Correct 4 ms 1116 KB Output is correct
9 Correct 4 ms 1116 KB Output is correct
10 Correct 4 ms 1148 KB Output is correct
11 Correct 3 ms 1324 KB Output is correct
12 Correct 3 ms 1324 KB Output is correct
13 Correct 3 ms 1344 KB Output is correct
14 Correct 4 ms 1444 KB Output is correct
15 Correct 3 ms 1492 KB Output is correct
16 Correct 4 ms 1548 KB Output is correct
17 Correct 3 ms 1596 KB Output is correct
18 Correct 3 ms 1748 KB Output is correct
19 Correct 2 ms 1748 KB Output is correct
20 Correct 2 ms 1748 KB Output is correct
21 Correct 2 ms 1748 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 11472 KB Output is correct
2 Correct 211 ms 17432 KB Output is correct
3 Correct 196 ms 23544 KB Output is correct
4 Correct 192 ms 28312 KB Output is correct
5 Correct 299 ms 35116 KB Output is correct
6 Correct 142 ms 38584 KB Output is correct
7 Correct 150 ms 43376 KB Output is correct
8 Correct 189 ms 50212 KB Output is correct
9 Correct 188 ms 56100 KB Output is correct
10 Correct 176 ms 60344 KB Output is correct
11 Correct 150 ms 64400 KB Output is correct
12 Correct 139 ms 69688 KB Output is correct
13 Correct 134 ms 74604 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 4 ms 700 KB Output is correct
3 Correct 4 ms 704 KB Output is correct
4 Correct 5 ms 812 KB Output is correct
5 Correct 4 ms 952 KB Output is correct
6 Correct 5 ms 952 KB Output is correct
7 Correct 4 ms 1116 KB Output is correct
8 Correct 4 ms 1116 KB Output is correct
9 Correct 4 ms 1116 KB Output is correct
10 Correct 4 ms 1148 KB Output is correct
11 Correct 3 ms 1324 KB Output is correct
12 Correct 3 ms 1324 KB Output is correct
13 Correct 3 ms 1344 KB Output is correct
14 Correct 4 ms 1444 KB Output is correct
15 Correct 3 ms 1492 KB Output is correct
16 Correct 4 ms 1548 KB Output is correct
17 Correct 3 ms 1596 KB Output is correct
18 Correct 3 ms 1748 KB Output is correct
19 Correct 2 ms 1748 KB Output is correct
20 Correct 2 ms 1748 KB Output is correct
21 Correct 2 ms 1748 KB Output is correct
22 Correct 191 ms 11472 KB Output is correct
23 Correct 211 ms 17432 KB Output is correct
24 Correct 196 ms 23544 KB Output is correct
25 Correct 192 ms 28312 KB Output is correct
26 Correct 299 ms 35116 KB Output is correct
27 Correct 142 ms 38584 KB Output is correct
28 Correct 150 ms 43376 KB Output is correct
29 Correct 189 ms 50212 KB Output is correct
30 Correct 188 ms 56100 KB Output is correct
31 Correct 176 ms 60344 KB Output is correct
32 Correct 150 ms 64400 KB Output is correct
33 Correct 139 ms 69688 KB Output is correct
34 Correct 134 ms 74604 KB Output is correct
35 Correct 195 ms 79396 KB Output is correct
36 Correct 212 ms 86220 KB Output is correct
37 Correct 207 ms 92400 KB Output is correct
38 Correct 209 ms 97732 KB Output is correct
39 Correct 207 ms 103136 KB Output is correct
40 Correct 223 ms 108536 KB Output is correct
41 Correct 218 ms 113716 KB Output is correct
42 Correct 213 ms 119320 KB Output is correct
43 Correct 205 ms 124036 KB Output is correct
44 Correct 216 ms 129800 KB Output is correct
45 Correct 196 ms 135244 KB Output is correct
46 Correct 202 ms 141992 KB Output is correct
47 Correct 148 ms 145020 KB Output is correct
48 Correct 141 ms 149744 KB Output is correct
49 Correct 178 ms 154744 KB Output is correct
50 Correct 152 ms 158496 KB Output is correct
51 Correct 137 ms 162828 KB Output is correct
52 Correct 153 ms 167452 KB Output is correct