제출 #1187248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187248		TIN	Progression (NOI20_progression)	C++20	100 / 100	1192 ms	115712 KiB

Progression

#include <bits/stdc++.h>

using namespace std;

#define FNAME "test"

typedef long long ll;

const int N = 3e5 + 5;

int n, q;
ll a[N];

struct Line {
	ll A, B;
	bool isNull;

	Line() : A(1), B(0), isNull(true) {}

	Line(ll A, ll B) : A(A), B(B), isNull((A == 1) && (B == 0)) {}

	Line operator + (const Line& oth) {
		if (isNull) return oth;
		if (oth.isNull) return *this;
		return Line(A * oth.A, A * oth.B + B);
	}

	Line& operator += (const Line& oth) {
		return *this = *this + oth;
	}

	ll operator () (ll x) const {
		return A * x + B;
	}
};

struct Node {
	int l, r;
	ll lValue, rValue;
	int mxsub, pre, suf;
	bool is_equal;
	bool isNull;

	Node() : l(0), r(0), lValue(0), rValue(0), mxsub(0), pre(0), suf(0), is_equal(false), isNull(true) {}

	Node(ll x, int pos) : l(pos), r(pos), lValue(x), rValue(x), mxsub(1), pre(1), suf(1), is_equal(true), isNull(false) {}

	Node operator + (Node oth) {
		if (isNull) return oth;
		if (oth.isNull) return *this;
		Node node;
		node.l = l;
		node.r = oth.r;
		node.lValue = lValue;
		node.rValue = oth.rValue;
		node.pre = pre;
		if (is_equal && rValue == oth.lValue) node.pre += oth.pre;
		node.suf = oth.suf;
		if (oth.is_equal && rValue == oth.lValue) node.suf += suf;
		node.mxsub = max(mxsub, oth.mxsub);
		if (rValue == oth.lValue) node.mxsub = max(node.mxsub, suf + oth.pre);
		if (is_equal && oth.is_equal && rValue == oth.lValue) node.is_equal = true;
		node.isNull = false;
		return node;
	}

	Node& operator += (const Node& oth) {
		return *this = *this + oth;
	}

	void apply(const Line& f) {
		lValue = f(lValue);
		rValue = f(rValue);
		if (f.A == 0) {
			mxsub = r - l + 1;
			pre = r - l + 1;
			suf = r - l + 1;
			is_equal = true;
		}
	}
};

Node ST[4 * N];
Line lazy[4 * N];

struct Line2 {
	ll A, B, C;

	Line2() : A(1), B(0), C(0) {}

	Line2(ll A, ll B, ll C) : A(A), B(B), C(C) {}

	bool is_null() {
		return (A == 1 && B == 0 && C == 0);
	}

	Line2 operator + (Line2 oth) {
		if (oth.is_null()) return *this;
		if (is_null()) return oth;
		return Line2(oth.A * A, oth.A * B + oth.B, oth.A * C + oth.C);
	}

	Line2& operator += (const Line2& oth) {
		return *this = *this + oth;
	}
};

ll ST2[4 * N];
Line2 lazy2[4 * N];

void Task() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	if (fopen(FNAME".inp","r")) {
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
	return;
}

void Input() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	return;
}

void build(int id, int l, int r) {
	if (l > r) return;
	lazy[id] = Line();
	if (l == r) {
		ST[id] = Node(a[r] - a[l - 1], l);
		return;
	}
	int m = (l + r) / 2;
	build(id * 2, l, m);
	build(id * 2 + 1, m + 1, r);
	ST[id] = ST[id * 2] + ST[id * 2 + 1];
	return;
}

void push(int id) {
	if (!lazy[id].isNull) {
		ST[id * 2].apply(lazy[id]); lazy[id * 2] = lazy[id] + lazy[id * 2];
		ST[id * 2 + 1].apply(lazy[id]); lazy[id * 2 + 1] = lazy[id] + lazy[id * 2 + 1];
		lazy[id] = Line();
	}
	return;
}

void update(int id, int l, int r, int u, int v, Line f) {
	if (v < l || r < u) return;
	if (u <= l && r <= v) {
		ST[id].apply(f);
		if (l < r) lazy[id] = f + lazy[id];
		return;
	}
	push(id);
	int m = (l + r) / 2;
	update(id * 2, l, m, u, v, f);
	update(id * 2 + 1, m + 1, r, u, v, f);
	ST[id] = ST[id * 2] + ST[id * 2 + 1];
	return;
}

Node query(int id, int l, int r, int u, int v) {
	if (v < l || r < u) return Node();
	if (u <= l && r <= v) return ST[id];
	push(id);
	int m = (l + r) / 2;
	return query(id * 2, l, m, u, v) + query(id * 2 + 1, m + 1, r, u, v);
}

ll sum(ll x) {
	return x * (x + 1) / 2;
}

ll arithmetic_sum(const Line2& L, ll len) {
	return L.C * len + sum(len - 1) * L.B;
}

void build2(int id, int l, int r) {
	lazy2[id] = Line2();
	if (l == r) {
		ST2[id] = a[l];
		return;
	}
	int m = (l + r) / 2;
	build2(id * 2, l, m);
	build2(id * 2 + 1, m + 1, r);
}

void push2(int id, int l, int r) {
	if (lazy2[id].is_null()) return;
	int m = (l + r) / 2;
	if (l == m) ST2[id * 2] = lazy2[id].A * ST2[id * 2] + arithmetic_sum(lazy2[id], m - l + 1);
	if (m + 1 == r) ST2[id * 2 + 1] = lazy2[id].A * ST2[id * 2 + 1] + arithmetic_sum(Line2(lazy2[id].A, lazy2[id].B, lazy2[id].C + lazy2[id].B * (m - l + 1)), r - m);
	lazy2[id * 2] += lazy2[id];
	lazy2[id * 2 + 1] += Line2(lazy2[id].A, lazy2[id].B, lazy2[id].C + lazy2[id].B * (m - l + 1));
	lazy2[id] = Line2();
}

void update2(int id, int l, int r, int u, int v, const Line2& L) {
	if (v < l || r < u) return;
	if (u <= l && r <= v) {
		if (l == r) ST2[id] = L.A * ST2[id] + arithmetic_sum(L, l - r + 1);
		lazy2[id] += L;
		return;
	}
	push2(id, l, r);
	int m = (l + r) / 2;
	update2(id * 2, l, m, u, v, L);
	if (u > m) update2(id * 2 + 1, m + 1, r, u, v, L);
	else update2(id * 2 + 1, m + 1, r, u, v, Line2(L.A, L.B, L.C + L.B * (m - max(u, l) + 1)));
	ST2[id] = ST2[id * 2] + ST2[id * 2 + 1];
}

ll query2(int id, int l, int r, int pos) {
	if (pos < l || r < pos) return 0LL;
	if (l == r) return ST2[id];
	push2(id, l, r);
	int m = (l + r) / 2;
	return ((pos <= m) ? query2(id * 2, l, m, pos) : query2(id * 2 + 1, m + 1, r, pos));
}

void solve() {
	while (q--) {
		int type; cin >> type;
		if (type == 1) {
			int l, r; ll A, B;
			cin >> l >> r >> A >> B;
			if (l < r) {
				Line L(1, B);
				update(1, 2, n, l + 1, r, L);
			}
			if (l > 1) update(1, 2, n, l, l, Line(1, A));
			if (r < n) update(1, 2, n, r + 1, r + 1, Line(1, - A - B * (r - l)));
			Line2 L2(1, B, A);
			update2(1, 1, n, l, r, L2);
		}
		if (type == 2) {
			int l, r; ll A, B;
			cin >> l >> r >> A >> B;
			if (l < r) {
				Line L(0, B);
				update(1, 2, n, l + 1, r, L);
			}
			if (l > 1) {
				ll vL = query2(1, 1, n, l - 1);
				update(1, 2, n, l, l, Line(0, A - vL));
			}
			if (r < n) {
				ll vR = query2(1, 1, n, r + 1);
				update(1, 2, n, r + 1, r + 1, Line(0, vR - A - B * (r - l)));
			}
			Line2 L2(0, B, A);
			update2(1, 1, n, l, r, L2);
		}
		if (type == 3) {
			int l, r;
			cin >> l >> r;
			if (l == r) cout << 1 << '\n';
			else cout << query(1, 2, n, l + 1, r).mxsub + 1 << '\n';
		}
	}
}

void Solve() {
	Input();
	build(1, 2, n);
	build2(1, 1, n);
	solve();
}

int main() {
	Task();
	Solve();
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Progression.cpp: In function 'void Task()':
Progression.cpp:115:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:116:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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