oj.uz

Submission #284286

# Submission time Handle Problem Language Result Execution time Memory
284286 2020-08-27T07:19:38 Z 임성재(#5754) Progression (NOI20_progression) C++17
0 / 100
 3 ms 512 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 1e9;
const ll INF = 1e18;

ll n, q;
ll d[100010];
pll tree[400010];
pll l[400010];
pll r[400010];
ll add[400010];
bool chk[400010];
ll cls[400010];
ll sum[400010];

void propagate(ll node, ll s, ll e) {
	if(!chk[node] && !add[node]) return;

	if(chk[node]) tree[node] = l[node] = r[node] = mp(e - s + 1, cls[node]), sum[node] = cls[node] * (e - s + 1);
	
	tree[node].se += add[node];
	l[node].se += add[node];
	r[node].se += add[node];
	sum[node] += add[node] * (e - s + 1);

	if(s != e) {
		if(chk[node]) {
			chk[node*2] = chk[node*2+1] = true;
			cls[node*2] = cls[node*2+1] = cls[node];
			add[node*2] = add[node*2+1] = 0;
		}

		add[node*2] += add[node];
		add[node*2+1] += add[node];
	}

	chk[node] = false;
	add[node] = 0;
}

void q1(ll node, ll s, ll e, ll L, ll R, ll x) {
	propagate(node, s, e);
	
	if(R < s || e < L) return;
	if(L <= s && e <= R) {
		chk[node] = true;
		cls[node] = x;

		propagate(node, s, e);
		
		return;
	}

	q1(node*2, s, (s+e)/2, L, R, x);
	q1(node*2+1, (s+e)/2+1, e, L, R, x);

	tree[node] = max(tree[node*2], tree[node*2+1]);
	if(l[node*2+1].se == r[node*2].se) tree[node] = max(tree[node], mp(l[node*2+1].fi + r[node*2].fi, l[node*2+1].se));
	
	l[node] = l[node*2];
	r[node] = r[node*2+1];

	if(l[node*2].se == l[node*2+1].se && l[node*2].fi == (s+e)/2 - s + 1) l[node].fi += l[node*2+1].fi;
	if(r[node*2].se == r[node*2+1].se && r[node*2+1].fi == e - (s+e)/2) r[node].fi += r[node*2].fi;

	sum[node] = sum[node*2] + sum[node*2+1];
}

void q2(ll node, ll s, ll e, ll L, ll R, ll x) {
	propagate(node, s, e);
	if(R < s || e < L) return;
	if(L <= s && e <= R) {
		add[node] += x;

		propagate(node, s, e);
		return;
	}

	q2(node*2, s, (s+e)/2, L, R, x);
	q2(node*2+1, (s+e)/2+1, e, L, R, x);

	tree[node] = max(tree[node*2], tree[node*2+1]);
	if(l[node*2+1].se == r[node*2].se) tree[node] = max(tree[node], mp(l[node*2+1].fi + r[node*2].fi, l[node*2+1].se));
	
	l[node] = l[node*2];
	r[node] = r[node*2+1];

	if(l[node*2].se == l[node*2+1].se && l[node*2].fi == (s+e)/2 - s + 1) l[node].fi += l[node*2+1].fi;
	if(r[node*2].se == r[node*2+1].se && r[node*2+1].fi == e - (s+e)/2) r[node].fi += r[node*2].fi;

	sum[node] = sum[node*2] + sum[node*2+1];
}

void cal(ll node, ll s, ll e, ll L, ll R, pll &tot, pll &lsum, pll &rsum) {
	propagate(node, s, e);
	
	if(R < s || e < L) {
		tot = lsum = rsum = mp(0, 0);
		return;
	}
	if(L <= s && e <= R) {
		tot = tree[node];
		lsum = l[node];
		rsum = r[node];

		return;
	}

	ll m = (s + e) / 2;

	if(R <= m) {
		cal(node*2, s, m, L, R, tot, lsum, rsum);
	}
	else if(L >= m+1) {
		cal(node*2+1, m+1, e, L, R, tot, lsum, rsum);
	}
	else {
		pll x, y, z, X, Y, Z;

		cal(node*2, s, m, L, R, x, y, z);
		cal(node*2+1, m+1, e, L, R, X, Y, Z);

		tot = max(x, X);

		if(Y.se == z.se) tot = max(tot, mp(Y.fi + z.fi, Y.se));
		
		lsum = y;
		rsum = Z;

		if(y.se == Y.se && y.fi == m - max(L, s) + 1) lsum.fi += Y.fi;
		if(z.se == Z.se && Z.fi == min(R, e) - m) rsum.fi += z.fi;
	}

	//cout << s << " " << e << " " << tot.fi << " " << tot.se << " " << lsum.fi << " " << lsum.se << " " << rsum.fi << " " << rsum.se << endl;
}

ll A(ll node, ll s, ll e, ll i) {
	propagate(node, s, e);

	if(i < s) return 0;
	if(e <= i) return sum[node];

	ll m = (s + e) / 2;
	return A(node*2, s, m, i) + A(node*2+1, m+1, e, i);
}

ll a(ll x) {
	return A(1, 1, n, x);
}

int main() {
	fast;

	cin >> n >> q;

	for(ll i=1; i<=n; i++) {
		cin >> d[i];

		q1(1, 1, n, i, i, d[i] - d[i-1]);
	}

	while(q--) {
		ll t, L, R;
		cin >> t >> L >> R;

		if(t == 1) {
			ll s, c;
			cin >> s >> c;

			q2(1, 1, n, L, L, s);
			if(L+1 <= R) q2(1, 1, n, L+1, R, c);
			if(R + 1 <= n) q2(1, 1, n, R+1, R+1, - s - (R - L) * c);
		}
		else if(t == 2) {
			ll s, c;
			cin >> s >> c;

			q1(1, 1, n, L, L, s - a(L-1));
			if(L+1 <= R) q1(1, 1, n, L+1, R, c);
			if(R + 1 <= n) q1(1, 1, n, R+1, R+1, a(R+1) - s - (R - L) * c);
		}
		else {
			pll x, y, z;

			cal(1, 1, n, L+1, R, x, y, z);

			cout << x.fi + 1 << "\n";
		}
	}
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -