oj.uz

답안 #679748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679748 2023-01-09T06:32:59 Z faribourz Sjeckanje (COCI21_sjeckanje) C++14
0 / 110
 1 ms 340 KB 
// Only GOD
// believe in yourself
// Nemidam Del Be In Darde Donya!
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define int ll
typedef long double ld;
typedef pair<int, int> pii;

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define bit(x, y) ((x >> y)&1)
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0

const int N = 2e5+100;
const int INF = 1e9+10;
int a[N];
int n;
int node[N << 2], node2[N << 2];
void upd(int x, int p){
	p += n;
	node[p] += x;
	node2[p] += x;
	p >>= 1;
	for(;p;p>>=1)
		node[p] = min(node[p*2], node[p*2+1]), node2[p] = max(node2[p*2], node2[p*2+1]);
}
pii get(int l, int r){
	l += n, r += n;
	int mx = 0, mn = INF;
	while(l < r){
		if(l & 1){
			mx = max(mx, node2[l]), mn = min(mn, node[l++]);
		}
		if(r & 1)
			mx = max(mx, node2[--r]), mn = min(mn, node[r]);
		l >>= 1, r >>= 1;
	}
	return {mn, mx};
}
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int q;
	cin >> n >> q;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	for(int i = 0 ;i < n; i++)
		upd(a[i], i);
	while(q--){
		int l, r, x;
		cin >> l >> r >> x;
		for(int i = l-1; i < r; i++)
			upd(x, i), a[i]+=x;
		int ans =0 ;
		for(int i = 0; i < n-1; i++){
			pii res = get(i, n);
			if(res.S - res.F == a[n-1] - a[i]){
				ans += a[n-1] - a[i];break;
			}
			ans += abs(a[i+1] - a[i]);
			i++;
		}
		cout << ans << '\n';
	}
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -