oj.uz

Submission #879601

# Submission time Handle Problem Language Result Execution time Memory
879601 2023-11-27T17:32:08 Z iskhakkutbilim Foehn Phenomena (JOI17_foehn_phenomena) C++17
30 / 100
 1000 ms 12884 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 1e9 + 7;
const int N = 2e5;

int n, q, S, T;
int lazy[4*N], t[4*N];
int a[N+10];
void push(int v, int vl, int vr){
	if(!lazy[v]) return;
	t[v]+= (lazy[v] * (vr-vl+1));
	if(vl != vr){
		lazy[v<<1]+= lazy[v];
		lazy[v<<1|1]+= lazy[v];	
	}
	lazy[v] = 0;
}

void add(int l, int r, int x, int v, int vl, int vr){
	push(v, vl, vr);
	if(l > vr or vl > r) return;
	if(l <= vl && r >= vr){
		lazy[v]+= x;
		push(v, vl, vr);
		return;
	}
	int mid = (vl + vr)>>1;
	add(l, r, x, v<<1, vl, mid);
	add(l, r, x, v<<1|1, mid+1, vr);
}

int get(int pos, int v, int vl, int vr){
	push(v, vl, vr);
	if(vl == vr) return t[v];
	int mid = (vl + vr)>>1;
	if(mid >= pos) return get(pos, v<<1, vl, mid);
	else return get(pos, v<<1|1, mid+1, vr);
}

int sum;
void degree(int idx){
	int A;
	int B = get(idx, 1, 1, n);
	if(idx == 1) A = 0;
	else A = get(idx-1, 1, 1, n);
	if(B > A){
		sum-= S * abs(B-A);
	}else{
		sum+= T * abs(B-A);
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> q >> S >> T;
	for(int i = 0;i <= n; i++){
		cin >> a[i];
		add(i, i, a[i], 1, 1, n);
	}
	for(int i = 1;i <= n; i++){
		degree(i);
	}
	
	while(q--){
		int l, r, x; cin >> l >> r >> x;
		add(l, r, x, 1, 1, n);
		sum = 0;
		for(int i = 1;i <= n; i++){
			degree(i);
		}
		
		cout << sum << '\n';
	}
	
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 2612 KB Output is correct
2 Correct 464 ms 2600 KB Output is correct
3 Correct 462 ms 2632 KB Output is correct
4 Correct 456 ms 2392 KB Output is correct
5 Correct 462 ms 2856 KB Output is correct
6 Correct 455 ms 2392 KB Output is correct
7 Correct 461 ms 2644 KB Output is correct
8 Correct 472 ms 2640 KB Output is correct
9 Correct 459 ms 2616 KB Output is correct
10 Correct 466 ms 2864 KB Output is correct
11 Correct 456 ms 2396 KB Output is correct
12 Correct 459 ms 2644 KB Output is correct
13 Correct 486 ms 2848 KB Output is correct
14 Correct 445 ms 2620 KB Output is correct
15 Correct 460 ms 2600 KB Output is correct
16 Correct 456 ms 2396 KB Output is correct
17 Correct 478 ms 2608 KB Output is correct
18 Correct 468 ms 2628 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 12884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 2612 KB Output is correct
2 Correct 464 ms 2600 KB Output is correct
3 Correct 462 ms 2632 KB Output is correct
4 Correct 456 ms 2392 KB Output is correct
5 Correct 462 ms 2856 KB Output is correct
6 Correct 455 ms 2392 KB Output is correct
7 Correct 461 ms 2644 KB Output is correct
8 Correct 472 ms 2640 KB Output is correct
9 Correct 459 ms 2616 KB Output is correct
10 Correct 466 ms 2864 KB Output is correct
11 Correct 456 ms 2396 KB Output is correct
12 Correct 459 ms 2644 KB Output is correct
13 Correct 486 ms 2848 KB Output is correct
14 Correct 445 ms 2620 KB Output is correct
15 Correct 460 ms 2600 KB Output is correct
16 Correct 456 ms 2396 KB Output is correct
17 Correct 478 ms 2608 KB Output is correct
18 Correct 468 ms 2628 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 Execution timed out 1056 ms 12884 KB Time limit exceeded
23 Halted 0 ms 0 KB -