oj.uz

답안 #864379

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
864379 2023-10-22T16:27:46 Z dsyz Foehn Phenomena (JOI17_foehn_phenomena) C++17
100 / 100
 420 ms 36736 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node{
	ll s, e, m, val, lazy;
	node *l, *r;
	node(ll S, ll E){
		s = S, e = E, m = (s+e)/2;
		val = 0;
		lazy = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propogate(){
		if(lazy==0) return;
		val += lazy*(e-s+1);
		if(s != e){ //not a leaf, send lazy tags to children (remember to write this if statement)
			l->lazy += lazy;
			r->lazy += lazy;
		}
		lazy = 0;
	}
	void update(ll S, ll E, ll V){
		propogate();
		if(s == S && e == E) lazy += V;
		else{
			if(E <= m) l->update(S, E, V);
			else if (m < S) r->update(S, E, V);
			else l->update(S, m, V),r->update(m+1, E, V);
			l->propogate(),r->propogate();
			val = l->val + r->val;
		}
	}
	ll query(ll S, ll E){
		propogate(); //remember to propogate
		if(s == S && e == E) return val; 
		else if(E <= m) return l->query(S, E); 
		else if(S >= m+1) return r->query(S, E);
		else return l->query(S, m) + r->query(m+1, E); 
	}
} *root;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,Q,S,T;
	cin>>N>>Q>>S>>T;
	root = new node(0,N + 5);
	ll A[N + 1];
	for(ll i = 0;i <= N;i++){
		cin>>A[i];
		root -> update(i,i,A[i]);
	}
	ll temperature = 0;
	for(ll i = 0;i < N;i++){
		if(A[i] < A[i + 1]) temperature -= abs(A[i + 1] - A[i]) * S;
		else temperature += abs(A[i] - A[i + 1]) * T;
	}
	for(ll q = 0;q < Q;q++){
		ll L,R,X;
		cin>>L>>R>>X;
		if(L > 0){
			ll A1 = root -> query(L - 1,L - 1);
			ll A2 = root -> query(L,L);
			if(A1 < A2) temperature += abs(A2 - A1) * S;
			else temperature -= abs(A1 - A2) * T;
			
			if(A1 < A2 + X) temperature -= abs((A2 + X) - A1) * S;
			else temperature += abs(A1 - (A2 + X)) * T;
		}
		if(R < N){
			ll A1 = root -> query(R,R);
			ll A2 = root -> query(R + 1,R + 1);
			if(A1 < A2) temperature += abs(A2 - A1) * S;
			else temperature -= abs(A1 - A2) * T;
			if(A1 + X < A2) temperature -= abs(A2 - (A1 + X)) * S;
			else temperature += abs((A1 + X) - A2) * T;
		}
		root -> update(L,R,X);
		cout<<temperature<<'\n';
	}
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 2 ms 780 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 420 ms 33824 KB Output is correct
2 Correct 389 ms 34388 KB Output is correct
3 Correct 394 ms 34964 KB Output is correct
4 Correct 391 ms 34352 KB Output is correct
5 Correct 386 ms 35616 KB Output is correct
6 Correct 178 ms 34664 KB Output is correct
7 Correct 170 ms 34644 KB Output is correct
8 Correct 338 ms 35384 KB Output is correct
9 Correct 336 ms 35728 KB Output is correct
10 Correct 372 ms 34388 KB Output is correct
11 Correct 156 ms 34340 KB Output is correct
12 Correct 169 ms 35340 KB Output is correct
13 Correct 170 ms 35408 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 2 ms 780 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 420 ms 33824 KB Output is correct
23 Correct 389 ms 34388 KB Output is correct
24 Correct 394 ms 34964 KB Output is correct
25 Correct 391 ms 34352 KB Output is correct
26 Correct 386 ms 35616 KB Output is correct
27 Correct 178 ms 34664 KB Output is correct
28 Correct 170 ms 34644 KB Output is correct
29 Correct 338 ms 35384 KB Output is correct
30 Correct 336 ms 35728 KB Output is correct
31 Correct 372 ms 34388 KB Output is correct
32 Correct 156 ms 34340 KB Output is correct
33 Correct 169 ms 35340 KB Output is correct
34 Correct 170 ms 35408 KB Output is correct
35 Correct 388 ms 33944 KB Output is correct
36 Correct 397 ms 35376 KB Output is correct
37 Correct 388 ms 36108 KB Output is correct
38 Correct 393 ms 35860 KB Output is correct
39 Correct 400 ms 36180 KB Output is correct
40 Correct 403 ms 36000 KB Output is correct
41 Correct 395 ms 35828 KB Output is correct
42 Correct 387 ms 35972 KB Output is correct
43 Correct 392 ms 35104 KB Output is correct
44 Correct 398 ms 35444 KB Output is correct
45 Correct 382 ms 35672 KB Output is correct
46 Correct 391 ms 36736 KB Output is correct
47 Correct 172 ms 35156 KB Output is correct
48 Correct 150 ms 35152 KB Output is correct
49 Correct 394 ms 34132 KB Output is correct
50 Correct 157 ms 34900 KB Output is correct
51 Correct 168 ms 35456 KB Output is correct
52 Correct 175 ms 35096 KB Output is correct