Submission #1165564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165564		sleepntsheep	Progression (NOI20_progression)	C++20	100 / 100	1309 ms	113248 KiB

Progression

#include <stdio.h>

int max1(int i, int j) {
	return i > j ? i : j;
}

int min1(int i, int j) {
	return i < j ? i : j;
}

#define N (1333333)

struct Line {
	using T = long long;
	T m, c;
	T operator()(T x) {
		return x * m + c;
	}

	Line friend operator+(const Line &a, const Line &b) {
		return Line{a.m + b.m, a.c + b.c};
	}

	void operator+=(const Line &o) {
		m += o.m;
		c += o.c;
	}

	Line friend operator*(const Line &a, T x) {
		return Line{a.m * x, a.c * x};
	}
};


struct {
	using T = long long;


	Line lza[N], lzb[N];
	bool fla[N], flb[N];
	Line t[N];

	void push(int v, int l, int r) {
		if (flb[v]) {
			t[v] = lzb[v];

			if (l != r) {
				lzb[2 * v + 1] = lzb[2 * v + 2] = lzb[v];
				lza[2 * v + 1] = lza[2 * v + 2] = Line{0, 0};
				fla[2 * v + 1] = fla[2 * v + 2] = 0;
				flb[2 * v + 1] = flb[2 * v + 2] = 1;
			}
		}

		if (fla[v]) {
			t[v] += lza[v];
			if (l != r) {
				lza[2 * v + 1] += lza[v];
				lza[2 * v + 2] += lza[v];
				fla[2 * v + 1] = fla[2 * v + 2] = 1;
			}
		}

		lza[v] = Line{0, 0};
		fla[v] = flb[v] = 0;
	}

	void range_add(int v, int l, int r, int x, int y, Line k) {
		push(v, l, r);
		if (r < x || y < l) return;
		if (x <= l && r <= y) {
			lza[v] = k;
			fla[v] = 1;
			push(v, l, r);
			return;
		}
		range_add(2 * v + 1, l, (l + r) / 2, x, y, k);
		range_add(2 * v + 2, (l + r) / 2 + 1, r, x, y, k);
	}

	void range_set(int v, int l, int r, int x, int y, Line k) {
		push(v, l, r);
		if (r < x || y < l) return;
		if (x <= l && r <= y) {
			lzb[v] = k;
			flb[v] = 1;
			push(v, l, r);
			return;
		}
		range_set(2 * v + 1, l, (l + r) / 2, x, y, k);
		range_set(2 * v + 2, (l + r) / 2 + 1, r, x, y, k);
	}

	T point_get(int v, int l, int r, int x) {
		push(v, l, r);
		if (l == r)
			return t[v](x);
		if (x <= (l + r) / 2)
			return point_get(2 * v + 1, l, (l + r) / 2, x);
		return point_get(2 * v + 2, (l + r) / 2 + 1, r, x);
	}
} discord;

struct {
	using T = long long;
	T lza[N], lzb[N];
	bool fla[N], flb[N];

	struct Node {
		T pv, sv;
		int sf = 1, pf = 1, ans =1;
		bool iden = 0;

		void p() const {
			return;
			printf(" Node{%d %d %d %d %d}\n", pv, pf, sv, sf, ans);
		}
	};

	Node merge(const Node &a, const Node &b, int l, int r) {
		if (a.iden) return b;
		if (b.iden) return a;
		int m = (l + r) / 2,
		    l1 = m - l + 1, l2 = r - m;

		Node c;
		c.iden = 0;

		c.pv = a.pv;
		c.pf = a.pf;

		if (l1 == a.pf && b.pv == a.pv) {
			c.pf += b.pf;
		}

		c.sv = b.sv;
		c.sf = b.sf;

		if (l2 == b.sf && b.sv == a.sv) {
			c.sf += a.sf;
		}

		c.ans = max1(max1(a.ans, b.ans), max1(c.sf, c.pf));
		if (b.pv == a.sv) {
			c.ans = max1(c.ans, b.pf + a.sf);
		}
		return c;
	}

	Node t[N];

	void push(int v, int l, int r) {
		if (flb[v]) {
			t[v].pv = t[v].sv = lzb[v];
			t[v].pf = t[v].sf = (r - l + 1);
			t[v].ans = r - l + 1;

			if (l != r) {
				lzb[2 * v + 1] = lzb[v];
				lzb[2 * v + 2] = lzb[v];
				flb[2 * v +1 ] = flb[2 * v + 2] = 1;
				lza[2 * v + 1] = lza[2 * v + 2] = 0;
			}
		}

		if (fla[v]) {
			t[v].pv += lza[v];
			t[v].sv += lza[v];

			if (l != r) {
				lza[2 * v + 1] += lza[v];
				lza[2 * v + 2] += lza[v];
				fla[2 * v +1 ] = fla[2 * v + 2] = 1;
			}
		}

		lza[v] = 0;
		fla[v] = flb[v] = 0;
	}

	void pull(int v, int l, int r) {
		int m = (l + r) / 2,
		    c1 = 2 * v + 2, c2 = 2 * v + 2,
		    l1 = m - l + 1, l2 = r - m;

		t[v] = merge(t[v * 2 + 1], t[v * 2 + 2], l, r);
	}

	void range_add(int v, int l, int r, int x, int y, T k) {
		push(v, l, r);
		if (r < x || y < l)
			return;

		if (x <= l && r <= y) {
			lza[v] = k;
			fla[v] = 1;
			push(v, l, r);
			return;
		}

		range_add(2 * v + 1, l, (l + r) / 2, x, y, k);
		range_add(2 * v + 2, (l + r) / 2 + 1, r, x, y, k);
		pull(v, l, r);
	}

	void range_set(int v, int l, int r, int x, int y, T k) {
		push(v, l, r);
		if (r < x || y < l)
			return;

		if (x <= l && r <= y) {
			lzb[v] = k;
			flb[v] = 1;
			push(v, l, r);
			return;
		}

		range_set(2 * v + 1, l, (l + r) / 2, x, y, k);
		range_set(2 * v + 2, (l + r) / 2 + 1, r, x, y, k);
		pull(v, l, r);
	}

	Node range_get(int v, int l, int r, int x, int y) {
		push(v, l, r);
		if (r < x || y < l) return Node{0, 0, 0, 0, 0, true};
		if (x <= l && r <= y) {
			t[v].p();
			return t[v];
		}

		return merge(range_get(2 * v + 1, l, (l + r) / 2, x, y)
				, range_get(2 * v + 2, (l + r) / 2 + 1, r, x, y), l, r);
	}

} miku;


int main() {
	int op, n, q, d, l, r, s, c, pd;

	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; ++i, pd = d) {
		scanf("%d", &d);
		discord.range_add(0, 1, n, i, i, Line{0, d});

		if (i > 1) {
			miku.range_add(0, 2, n, i, i, d - pd);
		}
	}

	for (int qq = q; qq--; ) {
		scanf("%d%d%d", &op, &l, &r);
		if (op < 3)
			scanf("%d%d", &c, &s);


		if (op == 1) {
			discord.range_add(0, 1, n, l, r, Line{s, c -l * 1ll * s});
			miku.range_add(0, 2, n, l + 1, r, s);
		} else if (op == 2) {
			discord.range_set(0, 1, n, l, r, Line{s, c
					- l * 1ll * s});
			miku.range_set(0, 2, n, l + 1, r, s);
		} else {
			if (l == r)
				puts("1");
			else {
				auto y = miku.range_get(0, 2, n, l + 1, r);
				y.p();
				printf("%d\n", y.ans + 1);
			}
		}

		if (op < 3) {
			if (l > 1) {
				miku.range_set(0, 2, n, l, l,
					discord.point_get(0, 1, n, l)
					- discord.point_get(0, 1, n, l - 1)
					      );
			}
			if (r + 1 <= n) {
				miku.range_set(0, 2, n, r + 1, r + 1,
						discord.point_get(0, 1, n, r + 1)
						- discord.point_get(0, 1, n, r)
					      );
			}
		}
	}


	return 0;
}

Compilation message (stderr)

Progression.cpp: In member function 'void<unnamed struct>::Node::p() const':
Progression.cpp:116:40: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  116 |                         printf(" Node{%d %d %d %d %d}\n", pv, pf, sv, sf, ans);
      |                                       ~^                  ~~
      |                                        |                  |
      |                                        int                long long int
      |                                       %lld
Progression.cpp:116:46: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
  116 |                         printf(" Node{%d %d %d %d %d}\n", pv, pf, sv, sf, ans);
      |                                             ~^                    ~~
      |                                              |                    |
      |                                              int                  long long int
      |                                             %lld
Progression.cpp: In function 'int main()':
Progression.cpp:241:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |         scanf("%d%d", &n, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~
Progression.cpp:243:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  243 |                 scanf("%d", &d);
      |                 ~~~~~^~~~~~~~~~
Progression.cpp:252:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  252 |                 scanf("%d%d%d", &op, &l, &r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:254:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  254 |                         scanf("%d%d", &c, &s);
      |                         ~~~~~^~~~~~~~~~~~~~~~

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