oj.uz

Submission #298784

# Submission time Handle Problem Language Result Execution time Memory
298784 2020-09-14T03:59:03 Z eggag32 Foehn Phenomena (JOI17_foehn_phenomena) C++17
100 / 100
 802 ms 19320 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

struct seg{
	ll dat[1 << 19];
	int sz;
	seg(int s){
		sz = s;
		for(int i = 0; i < (1 << 19); i++){
			dat[i] = 0;
		}
	}
	void update(int i, int s, int e, int x, ll v){
		if(s == e){
			dat[i] = v;
			return;
		}
		int m = (s + e) / 2;
		if(x <= m) update(i << 1, s, m, x, v);
		else update(i << 1 | 1, m + 1, e, x, v);
		dat[i] = dat[i << 1] + dat[i << 1 | 1];
	}
	void update(int x, ll v){
		update(1, 0, sz, x, v);
	}
	ll query(int i, int s, int e, int x, int y){
		if(e < x || y < s) return 0;
		if(x <= s && e <= y) return dat[i];
		int m = (s + e) / 2;
		return query(i << 1, s, m, x, y) + query(i << 1 | 1, m + 1, e, x, y);
	}
	ll query(int x, int y){
		return query(1, 0, sz, x, y);
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, q;
	ll s, t;	
	cin >> n >> q >> s >> t;
	vector<ll> a(n + 1);
	rep(i, n + 1) cin >> a[i];
	vector<ll> cnt(n + 1, 0LL);
	seg tree(n + 1);
	repn(i, 1, n + 1){
		if(a[i] > a[i - 1]){
			cnt[i] = -1 * s * (a[i] - a[i - 1]);
		}
		else{
			cnt[i] = t * (a[i - 1] - a[i]);
		}
		tree.update(i, cnt[i]);
	}
	vector<ll> num(n + 1, 0);
	vector<ll> num1(n + 1, 0);
	rep(i, q){
		int l, r;
		ll x;
		cin >> l >> r >> x;
		a[l] += x;
		if((a[l] + num[l - 1]) > (a[l - 1] + num1[l])){
			tree.update(l, -1 * s * (a[l] - a[l - 1] - num1[l] + num[l - 1]));
		}
		else{
			tree.update(l, t * (a[l - 1] - a[l] - num[l - 1] + num1[l]));
		}
		if(l != r) a[r] += x;
		if(r + 1 <= n){
			if((a[r + 1] + num[r]) > (a[r] + num1[r + 1])){
				tree.update(r + 1, -1 * s * ((a[r + 1] - num1[r + 1]) - a[r] + num[r]));
			}
			else{
				tree.update(r + 1, t * (a[r] - a[r + 1] - num[r] + num1[r + 1]));
			}
		}
		if(l + 1 < r) num[l] += x, num1[r] += x;
		cout << tree.query(0, n) << endl;
	}
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/

Subtask #1
30.0 / 30.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 12280 KB Output is correct
2 Correct 781 ms 16792 KB Output is correct
3 Correct 782 ms 17120 KB Output is correct
4 Correct 766 ms 17192 KB Output is correct
5 Correct 775 ms 18212 KB Output is correct
6 Correct 612 ms 18424 KB Output is correct
7 Correct 614 ms 18296 KB Output is correct
8 Correct 748 ms 18296 KB Output is correct
9 Correct 751 ms 18716 KB Output is correct
10 Correct 742 ms 17464 KB Output is correct
11 Correct 627 ms 18424 KB Output is correct
12 Correct 618 ms 18880 KB Output is correct
13 Correct 606 ms 19320 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4608 KB Output is correct
2 Correct 9 ms 4608 KB Output is correct
3 Correct 9 ms 4608 KB Output is correct
4 Correct 9 ms 4608 KB Output is correct
5 Correct 9 ms 4608 KB Output is correct
6 Correct 9 ms 4608 KB Output is correct
7 Correct 9 ms 4608 KB Output is correct
8 Correct 9 ms 4608 KB Output is correct
9 Correct 9 ms 4608 KB Output is correct
10 Correct 9 ms 4608 KB Output is correct
11 Correct 9 ms 4608 KB Output is correct
12 Correct 9 ms 4608 KB Output is correct
13 Correct 9 ms 4608 KB Output is correct
14 Correct 9 ms 4608 KB Output is correct
15 Correct 10 ms 4608 KB Output is correct
16 Correct 9 ms 4608 KB Output is correct
17 Correct 10 ms 4608 KB Output is correct
18 Correct 9 ms 4608 KB Output is correct
19 Correct 3 ms 4480 KB Output is correct
20 Correct 3 ms 4480 KB Output is correct
21 Correct 3 ms 4480 KB Output is correct
22 Correct 774 ms 12280 KB Output is correct
23 Correct 781 ms 16792 KB Output is correct
24 Correct 782 ms 17120 KB Output is correct
25 Correct 766 ms 17192 KB Output is correct
26 Correct 775 ms 18212 KB Output is correct
27 Correct 612 ms 18424 KB Output is correct
28 Correct 614 ms 18296 KB Output is correct
29 Correct 748 ms 18296 KB Output is correct
30 Correct 751 ms 18716 KB Output is correct
31 Correct 742 ms 17464 KB Output is correct
32 Correct 627 ms 18424 KB Output is correct
33 Correct 618 ms 18880 KB Output is correct
34 Correct 606 ms 19320 KB Output is correct
35 Correct 774 ms 17144 KB Output is correct
36 Correct 785 ms 18424 KB Output is correct
37 Correct 797 ms 19192 KB Output is correct
38 Correct 786 ms 18936 KB Output is correct
39 Correct 799 ms 19068 KB Output is correct
40 Correct 785 ms 19064 KB Output is correct
41 Correct 802 ms 18864 KB Output is correct
42 Correct 797 ms 18900 KB Output is correct
43 Correct 789 ms 18296 KB Output is correct
44 Correct 778 ms 18552 KB Output is correct
45 Correct 771 ms 18424 KB Output is correct
46 Correct 790 ms 19120 KB Output is correct
47 Correct 616 ms 19064 KB Output is correct
48 Correct 655 ms 18936 KB Output is correct
49 Correct 764 ms 18040 KB Output is correct
50 Correct 622 ms 18808 KB Output is correct
51 Correct 621 ms 19064 KB Output is correct
52 Correct 620 ms 18936 KB Output is correct