---
# System prepended metadata

title: INCLRX

---

# INCLRX

```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 15;
int a[N];
int h[N];
int n,m;
int pre[N];
int suf[N];
struct vl{
	int l,r,d;
}query[N];

signed main(){
	cin >> n >> m;
	for(int i=1; i<=m; i++){
		int l,r,d;
		cin >> l >> r >> d;
		h[l]+=d;
		h[r+1]-=d;
		query[i].l = l;
		query[i].r = r;
		query[i].d = d;
	}
	for(int i=1; i<=n; i++){
		h[i] += h[i-1];
	}
	pre[0] = -2e18;
	suf[n+1] = -2e18;
	int mx;
	for(int i=1; i<=n; i++){
		pre[i] = max(h[i], pre[i-1]);
	}
	for(int i=n; i>=1; i--){
		suf[i] = max(h[i], suf[i+1]);
	}
	mx = pre[n];
	int be;
	int ed;
	for(int i=1; i<=n; i++){
		if(h[i] == mx){
			be = i;
			break;
		}
	}
	for(int i=n; i>=1; i--){
		if(h[i] == mx){
			ed = i;
			break;
		}
	}
	int mn = mx;
	for(int i=1; i<=m; i++){
		if(query[i].l <= be and ed <= query[i].r){
			mn = min(mn, max(mx - query[i].d, max(pre[query[i].l - 1], suf[query[i].r + 1])));
		}
	}
	cout << mn;
}
```

# abc

```cpp=
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
string s;
int n;
int a[N],f[N];
int solve (char c) {
	int ans = 0;
	for (int i=1; i<=n; i++) {
		a[i] = a[i-1];
		if (s[i] == c) a[i] += 1;
		else a[i] -= 1;
		int l = 1, r = i, res = i;
		f[i] = min (f[i-1],a[i]);
		while (r >= l) {
			int mid = (r-l+1);
			if (a[i] - f[mid] > 0) {
				res = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		ans = max (ans,i-res);
	}
	return ans;
}
void go () {
	cin >> n >> s;
	s = "?" + s;
	int res = max ({solve('a'), solve('b'), solve ('c')});
	cout << res << endl;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	go();
}
```

# Trung bình

```cpp=
#include<bits/stdc++.h>
#define int long long 
#define double long double
using namespace std;

const int N = 1e5 + 15;
int n,k,h;
double a[N];
double pre[N];
double pre_min[N];

int bss(double x, int vl){
	int l=0;
	int r=vl;
	int mid;
	int res = -1;
	while(l <= r){
		mid = (l + r)/2;
		if(pre_min[mid] < x){
			r = mid - 1;
			res = mid;
		}
		else l = mid + 1;
	}
	return res;
}

int check(double mid){
	for(int i=1; i<=n; i++)a[i] -= mid;
	pre_min[0] = 0;
	for(int i=1; i<=n; i++){
		pre[i] = pre[i-1] + a[i];
		pre_min[i] = min(pre[i], pre_min[i-1]);
	}
	for(int i=1; i<=n; i++)a[i] += mid;
	int mx = 0;
	for(int i=1; i<=n; i++){
		int tmp = bss(pre[i],i);
		if(tmp == -1)continue;
		mx = max(mx, i - tmp);
	}
	if(mx >= k)return true;
	else return false;
}

signed main(){
	cin >> n >> k >> h;
	for(int i=1; i<=n; i++)cin >> a[i];
	double l = 0;
	double r = N;
	double mid;
	double res = (double)0;
	for(int i=1; i<=50; i++){
		mid = (l + r)/2;
		int tmp = check(mid);
		if(tmp == true){
			l = mid;
			res = mid;
		}
		else r = mid;
	}
	if(h == 0)cout << (int)res;
	else cout << setprecision(03) << fixed << res;
}
```