oj.uz

Submission #471029

# Submission time Handle Problem Language Result Execution time Memory
471029 2021-09-06T17:32:25 Z disastah Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 1491 ms 41276 KB 
#include <bits/stdc++.h>
#define ar array
#define fi first
#define se second
std::mt19937 rnd(237);
using namespace std;
typedef long double ld;
typedef long long ll;
const int inf=2e9+9;
const ll linf=4e18+18;
const int N=2e5;

struct fenw {
	vector<ll> f1, f2;
	int n;
	fenw(int n=0): n(n) {
		f1.assign(n+1,0LL), f2=f1;
	}
	void upd(vector<ll>&f, int p, ll x) { ++p;
		for (; p<=n; p+=(p&-p)) f[p]+=x;
	}
	void rng_upd(int l, int r, ll x) {
		upd(f1,l,x), upd(f1,r,-x);
		upd(f2,l,x*l), upd(f2,r,-x*r);
	}
	ll sum(int p, ll ans=0) {
		int p1=p;
		for (; p; p-=(p&-p)) ans+=f1[p]*p1-f2[p];
		return ans;
	}
	ll get(int p) {return sum(p+1)-sum(p);}
};
struct segtr {
	vector<ll> a;
	vector<ar<ar<ll,2>,2>> t;
	fenw fw;
	int n;
	segtr(ll *x, int n): n(n) {
		fw={n};
		a.resize(n);
		for (int i=0; i<n; ++i) {
			a[i]=x[i];
			fw.rng_upd(i,i+1,a[i]);
		}
		t.resize(n*4);
	}
	void calc(int v, int l, int r) {
		int m=(l+r)/2;
		ll am=fw.get(m), am_1=fw.get(m-1), am1=(m+1==n?0:fw.get(m+1));
		for (auto x : {0,1}) {
			for (auto y : {0,1}) {
				t[v][x][y]=max(max(t[2*v+1][x][0]+t[2*v+2][0][y],
								t[2*v+1][x][1]+t[2*v+2][0][y]),
								t[2*v+1][x][0]+t[2*v+2][1][y]);
				if (m+1==n||(am_1<am&&am<am1)||(am_1>am&&am>am1)) {
					t[v][x][y]=max(t[v][x][y],t[2*v+1][x][1]+t[2*v+2][1][y]);
				}
			}
		}
	}
	void build(int v, int l, int r) {
		if (l+1==r) {
			t[v][0][0]=0;
			t[v][0][1]=-4e13;
			t[v][1][0]=-4e13;
			t[v][1][1]=(r==n?0:abs(a[l]-a[r]));
		}
		else {
			int m=(l+r)/2;
			build(2*v+1,l,m);
			build(2*v+2,m,r);
			calc(v,l,r);
		}
	} void build() {build(0,0,n);}
	void upd(int v, int tl, int tr, int l, int r) {
		if (r<=tl||tr<l) return;
		if (l<=tl&&tr<r) return;
		if (tl+1==tr) t[v][1][1]=(tr==n?0:abs(fw.get(tl)-fw.get(tr)));
		else {
			int tm=(tl+tr)/2;
			upd(2*v+1,tl,tm,l,r);
			upd(2*v+2,tm,tr,l,r);
			calc(v,tl,tr);
		}
	} void upd(int l, int r, ll x) {
		fw.rng_upd(l,r,x);
		upd(0,0,n,l,r);
	}
};

int n, q;
ll a[N];

void solve() {
	cin >> n >> q;
	for (int i=0; i<n; ++i) cin >> a[i];
	segtr tr(a,n); tr.build();
	while(q--){
		int l, r, x; cin >> l >> r >> x; --l;
		tr.upd(l,r,x);
		cout << max(max(tr.t[0][0][0],tr.t[0][0][1]),max(tr.t[0][1][0],tr.t[0][1][1])) << "\n";
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
#ifdef disastah
	cout << "Output\n\n";
#endif
/*#ifndef disastah
	freopen("marathon.in","r",stdin);
	freopen("marathon.out","w",stdout);
#endif*/
	int tt=1;
//	cin >> tt;
	while (tt--) {
		solve();
		cout << "\n";
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 10 ms 932 KB Output is correct
8 Correct 11 ms 920 KB Output is correct
9 Correct 10 ms 932 KB Output is correct
10 Correct 10 ms 844 KB Output is correct
11 Correct 10 ms 844 KB Output is correct
12 Correct 10 ms 844 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 10 ms 932 KB Output is correct
8 Correct 11 ms 920 KB Output is correct
9 Correct 10 ms 932 KB Output is correct
10 Correct 10 ms 844 KB Output is correct
11 Correct 10 ms 844 KB Output is correct
12 Correct 10 ms 844 KB Output is correct
13 Correct 1464 ms 40768 KB Output is correct
14 Correct 1483 ms 40936 KB Output is correct
15 Correct 1442 ms 40708 KB Output is correct
16 Correct 1450 ms 40652 KB Output is correct
17 Correct 1491 ms 40660 KB Output is correct
18 Correct 1419 ms 41276 KB Output is correct