Submission #317764

#	Time	Username	Problem	Language	Result	Execution time	Memory
317764		parsabahrami	Progression (NOI20_progression)	C++17	100 / 100	1993 ms	95400 KiB

Progression

//! The Leader Of Retards Bemola
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define lc 							id << 1
#define rc 							lc | 1

ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
        if (b & 1)
            ans = ans * a % md;
    return ans % md;
}
const ll MAXN = 3e5 + 10;
const ll INF  = 8e18;
const ll MOD  = 1e9 + 7;
ll lazy[2][MAXN << 2], A[MAXN], n, q;

struct Node {
	ll sum, L, R, cntL, cntR, mx, l, r;

	friend Node operator+(const Node x, const Node y) {
		if (y.l == -1) return x;
		if (x.l == -1) return y;
		Node ans; ans.sum = x.sum + y.sum; ans.l = x.l, ans.r = y.r;
		ans.L = x.L, ans.cntL = x.cntL;
		ans.R = y.R, ans.cntR = y.cntR;
		ans.mx = max(x.mx, y.mx);
		if (x.cntL == x.r - x.l && x.L == y.L) ans.cntL = x.cntL + y.cntL;
		if (y.cntR == y.r - y.l && x.R == y.R) ans.cntR = x.cntR + y.cntR;
		if (x.R == y.L) ans.mx = max(ans.mx, x.cntR + y.cntL);
		return ans;
	}
};

Node seg[MAXN << 2], emp;

void build(ll id = 1, ll l = 1, ll r = n + 1) {
	if (r - l == 1) {
		seg[id].l = l, seg[id].r = r;
		seg[id].mx = seg[id].cntL = seg[id].cntR = 1;
		seg[id].sum = seg[id].L = seg[id].R = A[l];
		return;
	}
	ll mid = (l + r) >> 1;
	build(lc, l, mid);
	build(rc, mid, r);
	seg[id] = seg[lc] + seg[rc];
}

void shift(ll id, ll l, ll r) {
	if (lazy[0][id] == 0) return;
	if (lazy[0][id] == 1) {
		seg[id].sum += lazy[1][id] * (r - l);
		seg[id].L += lazy[1][id];
		seg[id].R += lazy[1][id];
		if (r - l > 1) {
			if (lazy[0][lc] == 0) lazy[0][lc] = lazy[0][id];
			lazy[1][lc] += lazy[1][id];
			if (lazy[0][rc] == 0) lazy[0][rc] = lazy[0][id];
			lazy[1][rc] += lazy[1][id];
		}
	} else {
		seg[id].sum = lazy[1][id] * (r - l);
		seg[id].mx = seg[id].cntL = seg[id].cntR = r - l;
		seg[id].L = seg[id].R = lazy[1][id];
		if (r - l > 1) {
			lazy[0][lc] = lazy[0][rc] = lazy[0][id];
			lazy[1][lc] = lazy[1][rc] = lazy[1][id];
		}
	}
	lazy[0][id] = lazy[1][id] = 0;
}

void update(ll ql, ll qr, ll t, ll x, ll id = 1, ll l = 1, ll r = n + 1) {
	shift(id, l, r);
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr) {
		lazy[0][id] = t, lazy[1][id] = x;
		return shift(id, l, r);
	}
	ll mid = (l + r) >> 1;
	shift(lc, l, mid), shift(rc, mid, r);
	update(ql, qr, t, x, lc, l, mid);
	update(ql, qr, t, x, rc, mid, r);
	seg[id] = seg[lc] + seg[rc];
}

Node get(ll ql, ll qr, ll id = 1, ll l = 1, ll r = n + 1) {
	shift(id, l, r);
	if (qr <= l || r <= ql) return emp;
	if (ql <= l && r <= qr) return seg[id];
	ll mid = (l + r) >> 1;
	shift(lc, l, mid), shift(rc, mid, r);
	return get(ql, qr, lc, l, mid) + get(ql, qr, rc, mid, r);
}

int main() {
	emp.l = -1;
	scanf("%lld%lld", &n, &q);
	for (ll i = 1; i <= n; i++) {
		scanf("%lld", &A[i]);
	}
	for (ll i = n; i >= 1; i--) {
		A[i] = A[i] - A[i - 1];
	}
	build();
	while (q--) {
		ll t, l, r, s, c;
		scanf("%lld", &t);
		if (t == 1) {
			scanf("%lld%lld%lld%lld", &l, &r, &s, &c);
			ll x = get(1, r + 2).sum;
			update(l + 1, r + 1, 1, c);
			update(l, l + 1, 1, s);
			update(r + 1, r + 2, 2, x - get(1, r + 1).sum);
		} else if (t == 2) {
			scanf("%lld%lld%lld%lld", &l, &r, &s, &c);
			ll x = get(1, r + 2).sum;
			update(l + 1, r + 1, 2, c);
			update(l, l + 1, 2, -get(1, l).sum + s);
			update(r + 1, r + 2, 2, x - get(1, r + 1).sum);
		} else {
			scanf("%lld%lld", &l, &r);
			if (r == l) printf("%lld\n", 1LL);
			else printf("%lld\n", get(l + 1, r + 1).mx + 1);
		}
	}
    return 0;
}

Compilation message (stderr)

Progression.cpp: In function 'int main()':
Progression.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |  scanf("%lld%lld", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
Progression.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |   scanf("%lld", &A[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
Progression.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |   scanf("%lld", &t);
      |   ~~~~~^~~~~~~~~~~~
Progression.cpp:120:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  120 |    scanf("%lld%lld%lld%lld", &l, &r, &s, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:126:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |    scanf("%lld%lld%lld%lld", &l, &r, &s, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:132:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |    scanf("%lld%lld", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17