Submission #261264

#	Time	Username	Problem	Language	Result	Execution time	Memory
261264		Berted	Progression (NOI20_progression)	C++14	100 / 100	1885 ms	127056 KiB

Progression

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define fst first
#define snd second
using namespace std;

const ll INF = 1e18;

const int SZ = (1 << 20) + 69;

inline pii getLine(pii p1, pii p2)
{
	assert(p1.fst + 1 == p2.fst);
	return {p2.snd - p1.snd, p1.snd * (1 + p1.fst) - p2.snd * p1.fst};
}

inline pii addLine(pii l1, pii l2) {return {l1.fst + l2.fst, l1.snd + l2.snd};}

inline pii getP(pii l, ll x) {return {x, l.fst * x + l.snd};}

struct node
{
	pii lp = {INF, INF}, rp = {INF, INF}, lq = {INF, INF}, rq = {INF, INF};
	int pl = 0, sl = 0, mxl = 0;

	node() {}
};

node seg[SZ];
pii lz[SZ][2];

inline void merge(node &p, node l, node r)
{
	if (l.lp.fst == INF) {p = r;}
	else if (r.lp.fst == INF) {p = l;}
	else
	{
		p.lp = l.lp; p.rp = r.rp;

		pii cl = getLine(l.rp, r.lp);
		int nwsz = 1 + (cl == l.rq) * l.sl + (cl == r.lq) * r.pl; 

		if (l.lq.fst == INF) {p.lq = cl;}
		else {p.lq = l.lq;}

		if (r.rq.fst == INF) {p.rq = cl;}
		else {p.rq = r.rq;}

		if (l.lq.fst == INF) {p.pl = nwsz;}
		else if (l.pl == l.rp.fst - l.lp.fst && l.rq == cl) {p.pl = nwsz;}
		else {p.pl = l.pl;}

		if (r.rq.fst == INF) {p.sl = nwsz;}
		else if (r.sl == r.rp.fst - r.lp.fst && r.lq == cl) {p.sl = nwsz;}
		else {p.sl = r.sl;}

		p.mxl = max({l.mxl, r.mxl, nwsz});
	}
}

inline void lazyDrop(pii a, pii b, int idx)
{
	if (a != make_pair(INF, INF))
	{
		lz[idx][0] = a;
		lz[idx][1] = make_pair(0, 0);
	}
	else if (b != make_pair(0LL, 0LL))
	{
		if (lz[idx][0] != make_pair(INF, INF)) {lz[idx][0] = addLine(lz[idx][0], b);}
		else {lz[idx][1] = addLine(lz[idx][1], b);}
	}
}

inline void prop(int idx, int L, int R)
{
	if (L <= R)
	{
		if (lz[idx][0] != make_pair(INF, INF))
		{
			seg[idx].lp = getP(lz[idx][0], seg[idx].lp.fst);
			seg[idx].rp = getP(lz[idx][0], seg[idx].rp.fst);
			if (R > L)
			{
				seg[idx].lq = lz[idx][0];
				seg[idx].rq = lz[idx][0];
			}
			seg[idx].pl = R - L;
			seg[idx].sl = R - L;
			seg[idx].mxl = R - L;
		} 
		else if (lz[idx][1] != make_pair(0LL, 0LL))
		{
			seg[idx].lp.snd += getP(lz[idx][1], seg[idx].lp.fst).snd;
			seg[idx].rp.snd += getP(lz[idx][1], seg[idx].rp.fst).snd;
			if (R > L)
			{
				seg[idx].lq = addLine(lz[idx][1], seg[idx].lq);
				seg[idx].rq = addLine(lz[idx][1], seg[idx].rq);
			}
		}
		if (L < R)
		{
			lazyDrop(lz[idx][0], lz[idx][1], 2 * idx);
			lazyDrop(lz[idx][0], lz[idx][1], 2 * idx + 1);
		}
		lz[idx][0] = make_pair(INF, INF);
		lz[idx][1] = make_pair(0, 0);
	}
}

int n, q, ar[300001];

void bld(int idx, int L, int R)
{
	if (L < R)
	{
		lz[idx][0] = make_pair(INF, INF);
		lz[idx][1] = make_pair(0LL, 0LL);
		int M = L + R >> 1;
		bld(2 * idx, L, M);
		bld(2 * idx + 1, M + 1, R);
		merge(seg[idx], seg[2 * idx], seg[2 * idx + 1]);
	}
	else if (L == R)
	{
		lz[idx][0] = make_pair(INF, INF);
		lz[idx][1] = make_pair(0LL, 0LL);
		seg[idx].lp = {L, ar[L]};
		seg[idx].rp = seg[idx].lp;
	}
	/*cout << "--- " << L << "  " << R << " --\n";
	cout << seg[idx].lp.fst << ", " << seg[idx].lp.snd << "\n";
	cout << seg[idx].rp.fst << ", " << seg[idx].rp.snd << "\n";
	cout << seg[idx].lq.fst << ", " << seg[idx].lq.snd << "\n";
	cout << seg[idx].rq.fst << ", " << seg[idx].rq.snd << "\n";
	cout << seg[idx].pl << "  " << seg[idx].sl << "  " << seg[idx].mxl << "\n";*/
}

void upd(int idx, int L, int R, int l, int r, int t, pii val)
{
	prop(idx, L, R);
	if (l <= r)
	{
		if (L == l && R == r) 
		{
			if (t == 0) {lazyDrop(val, {0, 0}, idx); prop(idx, L, R);}
			else {lazyDrop({INF, INF}, val, idx); prop(idx, L, R);}
		}
		else
		{
			int M = L + R >> 1;
			upd(2 * idx, L, M, l, min(M, r), t, val);
			upd(2 * idx + 1, M + 1, R, max(M + 1, l), r, t, val);
			merge(seg[idx], seg[2 * idx], seg[2 * idx + 1]);
		}
	}
}

node qry(int idx, int L, int R, int l, int r)
{
	if (l <= r)
	{
		prop(idx, L, R);
		if (L == l && R == r) return seg[idx];
		else
		{
			node ret; int M = L + R >> 1;
			merge(ret, qry(2 * idx, L, M, l, min(M, r)), qry(2 * idx + 1, M + 1, R, max(M + 1, l), r));
			return ret;
		}
	}
	return node();
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> ar[i];
	bld(1, 1, n);
	for (int i = 0; i < q; i++)
	{
		int t; cin >> t;
		if (t < 3)
		{
			ll l, r, s, c; cin >> l >> r >> s >> c;
			t = !(t - 1);
			upd(1, 1, n, l, r, t, make_pair(c, s - c * l));
		}
		else 
		{
			int l, r; cin >> l >> r;
			cout << qry(1, 1, n, l, r).mxl + 1 << "\n";
		}
	}
	return 0;
}

Compilation message (stderr)

Progression.cpp: In function 'void bld(int, int, int)':
Progression.cpp:121:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int M = L + R >> 1;
           ~~^~~
Progression.cpp: In function 'void upd(int, int, int, int, int, int, std::pair<long long int, long long int>)':
Progression.cpp:153:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int M = L + R >> 1;
            ~~^~~
Progression.cpp: In function 'node qry(int, int, int, int, int)':
Progression.cpp:169:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    node ret; int M = L + R >> 1;
                      ~~^~~

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