답안 #538126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538126	2022-03-16T06:05:30 Z	blue	Progression (NOI20_progression)	C++17	68 / 100	869 ms	71472 KB

Progression

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using vll = vector<ll>;


int N, Q;
vll diff;


struct Node
{
	int l, r;

	ll lp = 0; //lp (everything below already includes lp)
	int ns = 1; //node size

	bool ih = 0; //is homogenous (if homogenous, adjust everything below!)

	ll fv = 0; //first value
	int fs = 1; //first size

	ll lv = 0; //last value
	int ls = 1; //last size

	int ts = 1; //total size

	ll sm = 0; //post lp
};

Node singlenode(int i)
{
	return {i, i, 0, 1, 1, diff[i], 1, diff[i], 1, 1, diff[i]};
}

Node combine(Node& A, Node& B)
{
	Node res;

	res.l = A.l;
	res.r = B.r;

	res.lp = 0;
	res.ns = A.ns + B.ns;
	res.ih = 0;

	res.fv = A.fv;
	if(A.fs == A.ns && B.fv == A.fv)
		res.fs = A.fs + B.fs;
	else
		res.fs = A.fs;

	res.lv = B.lv;
	if(B.ls == B.ns && A.lv == B.lv)
		res.ls = A.ls + B.ls;
	else
		res.ls = B.ls;

	res.ts = max(A.ts, B.ts);
	if(A.lv == B.fv)
		res.ts = max(res.ts, A.ls + B.fs);

	res.sm = A.sm + B.sm;

	// cerr << "combine " << A.l << ' ' << A.r << ' ' << A.lv << ' ' << A.ls << " with " << B.l << ' ' << B.r << ' ' << B.fv << ' ' << B.fs << "\n";
	return res;
}

Node combine2(Node A, Node B)
{
	return combine(A, B);
}

void add(Node& A, ll V)
{
	A.lp += V;
	A.fv += V;
	A.lv += V;
	A.sm += V * A.ns;
}

void set(Node& A, ll V)
{
	A.lp = 0;
	A.ih = 1;

	A.fv = A.lv = V;
	A.fs = A.ls = A.ts = A.ns;
	A.sm = A.ns * V;
}



struct segtree
{
	Node v;
	segtree* left = NULL;
	segtree* right = NULL;

	segtree()
	{
		;
	}

	segtree(int L, int R)
	{
		if(L == R) v = singlenode(L);
		else
		{
			left = new segtree(L, (L+R)/2);
			right = new segtree((L+R)/2+1, R);
			v = combine(left->v, right->v);
		}

		// cerr << "Node = " << L << ' ' << R << '\n';
		// cerr << v.fv << ' ' << v.fs << "  " << v.lv << ' ' << v.ls << '\n';
		// cerr << v.ts << '\n';
	}

	void pushdown()
	{
		if(v.ih)
		{
			v.ih = 0;
			set(left->v, v.fv);
			set(right->v, v.fv);
		}
		else
		{
			add(left->v, v.lp);
			add(right->v, v.lp);
			v.lp = 0;
		}
	}

	ll rangesum(int L, int R)
	{
		if(R < v.l || v.r < L) return 0;
		else if(L <= v.l && v.r <= R)
		{
			return v.sm;
		}
		else
		{
			pushdown();
			return left->rangesum(L, R) + right->rangesum(L, R);
		}
	}

	Node getRange(int L, int R)
	{
		if(L <= v.l && v.r <= R) return v;
		else 
		{
			pushdown();
			if(L <= left->v.r && right->v.l <= R) return combine2(left->getRange(L, R), right->getRange(L, R));
			else if(L <= left->v.r) return left->getRange(L, R);
			else return right->getRange(L, R);
		}
	}

	void rangeadd(int L, int R, ll V)
	{
		if(L <= v.l && v.r <= R) add(v, V);
		else
		{
			pushdown();
			if(L <= left->v.r) left->rangeadd(L, R, V);
			if(right->v.l <= R) right->rangeadd(L, R, V);
			v = combine(left->v, right->v);
		}
	}

	void rangeset(int L, int R, ll V)
	{
		// cerr << "range set " << L << ' ' << R << ' ' << V << " at " << 
		if(L <= v.l && v.r <= R) set(v, V);
		else
		{
			pushdown();
			if(L <= left->v.r) left->rangeset(L, R, V);
			if(right->v.l <= R) right->rangeset(L, R, V);
			v = combine(left->v, right->v);
		}

		// cerr << "new range " << v.l << ' ' << v.r << " = " << v.fv << ' ' << v.lv << '\n';
 	}
};




int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> Q;

	vll D(1+N);
	for(int i = 1; i <= N; i++) cin >> D[i];

	// ll adj = D[1];
	// for(int i = 1; i <= N; i++) D[i] -= adj;

	if(N == 1)
	{
		for(int j = 1; j <= Q; j++)
		{
			int Z;
			cin >> Z;

			int u;
			if(Z <= 2) cin >> u >> u >> u >> u;
			else
			{
				cin >> u >> u;
				cout << 1 << '\n';
			}
		}
		return 0;
	}

	diff = vll(1+N);
	for(int i = 1; i <= N-1; i++) diff[i] = D[i+1] - D[i];

	segtree ST(1, N-1);

	// for(int i = 1; i <= N-1; i++) cerr << diff[i] << ' ';
	// 	cerr << '\n';

	// cerr << "done \n";

	ll A0 = D[1];

	for(int j = 1; j <= Q; j++)
	{
		// cerr << "\n\n\n\n\n\n";
		ll o;
		cin >> o;

		if(o == 1)
		{
			ll L, R, S, C;
			cin >> L >> R >> S >> C;

			if(L > 1)
				ST.rangeadd(L-1, L-1, S);

			if(R < N)
				ST.rangeadd(R, R, -(S + (R-L)*C));

			if(L < R)
				ST.rangeadd(L, R-1, C);

			if(L == 1) A0 += S;
		}
		else if(o == 2)
		{
			ll L, R, S, C;
			cin >> L >> R >> S >> C;
			// S -= adj;

			ll SL = ST.rangesum(1, L-1);
			ll SR = ST.rangesum(1, R);

			if(L > 1)
			{
				// cerr << "A rangeset " << L-1 << ' ' << L-1 << ' ' << S - ST.rangesum(1, L-2) << '\n';
				// ST.rangeset(L-1, L-1, S - (A0 + ST.rangesum(1, L-2)));
				// cerr << "rangesum = " << ST.rangesum(1, L-2) << '\n';
				// cerr << "set " << L-1 << " : " << S - ST.rangesum(1, L-2) << '\n';

				ST.rangeadd(L-1, L-1, S - (A0 + SL));
			}

			if(R < N)
			{
				// cerr << "right rangesum = " << ST.rangesum(1, R-1) << '\n';
				// cerr << "right diff = " << ST.rangesum(1, R-1) - (S + (R-L)*C) << '\n';
				// cerr << "rangesum = " << ST.rangesum(1, R-1) << '\n';
				// cerr << "right element = " << S+(R-L)*C << '\n';
				// ST.rangeadd(R, R, ST.rangesum(1, R-1) - (S + (R-L)*C));

				// cerr << "B rangeset " << R << ' ' << R << " : " << ST.rangesum(1, R) - (S + (R-L)*C) << '\n';
				// cerr << ST.rangesum(1, R) << ' ' << S+(R-L)*C << '\n';
				// ST.rangeset(R, R, A0 + ST.rangesum(1, R) - (S + (R-L)*C));

				ST.rangeset(R, R, A0 + SR - (S + (R-L)*C));
			}

			if(L < R)
			{
				// cerr << "ST range set " << L << ' ' << R-1 << ' ' << C << '\n';
				ST.rangeset(L, R-1, C);
			}

			if(L == 1) A0 = S;
		}
		else if(o == 3)
		{
			int L, R;
			cin >> L >> R;

			if(L == R) cout << 1 << '\n';
			else
			{
				cout << ST.getRange(L, R-1).ts + 1 << '\n';
			}
		}
	}
}

Subtask #1

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	169 ms	62028 KB	Output is correct
2	Correct	80 ms	544 KB	Output is correct
3	Correct	82 ms	508 KB	Output is correct
4	Correct	93 ms	608 KB	Output is correct
5	Correct	109 ms	648 KB	Output is correct
6	Correct	80 ms	588 KB	Output is correct
7	Correct	74 ms	588 KB	Output is correct
8	Correct	1 ms	324 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	169 ms	61996 KB	Output is correct
12	Correct	167 ms	61900 KB	Output is correct
13	Correct	153 ms	62256 KB	Output is correct
14	Correct	176 ms	62416 KB	Output is correct
15	Correct	165 ms	62264 KB	Output is correct
16	Correct	195 ms	61984 KB	Output is correct
17	Correct	169 ms	62060 KB	Output is correct
18	Correct	158 ms	61984 KB	Output is correct

Subtask #2

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	468 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	333 ms	62416 KB	Output is correct
2	Correct	88 ms	844 KB	Output is correct
3	Correct	87 ms	952 KB	Output is correct
4	Correct	75 ms	904 KB	Output is correct
5	Correct	81 ms	1012 KB	Output is correct
6	Correct	88 ms	912 KB	Output is correct
7	Correct	88 ms	912 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	437 ms	62248 KB	Output is correct
12	Correct	318 ms	62640 KB	Output is correct
13	Correct	412 ms	62248 KB	Output is correct
14	Correct	430 ms	62248 KB	Output is correct
15	Correct	306 ms	62400 KB	Output is correct
16	Correct	448 ms	62924 KB	Output is correct
17	Correct	469 ms	62748 KB	Output is correct
18	Correct	422 ms	62912 KB	Output is correct
19	Correct	323 ms	62156 KB	Output is correct
20	Correct	363 ms	62236 KB	Output is correct
21	Correct	350 ms	62140 KB	Output is correct

Subtask #4

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	622 ms	61676 KB	Output is correct
2	Correct	136 ms	3556 KB	Output is correct
3	Correct	167 ms	3604 KB	Output is correct
4	Correct	126 ms	3532 KB	Output is correct
5	Correct	169 ms	3636 KB	Output is correct
6	Correct	136 ms	3596 KB	Output is correct
7	Correct	139 ms	3664 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	709 ms	67952 KB	Output is correct
12	Correct	680 ms	71176 KB	Output is correct
13	Correct	675 ms	67992 KB	Output is correct
14	Correct	679 ms	68032 KB	Output is correct
15	Correct	599 ms	71116 KB	Output is correct
16	Correct	704 ms	71472 KB	Output is correct
17	Correct	729 ms	71272 KB	Output is correct
18	Correct	717 ms	71324 KB	Output is correct
19	Correct	677 ms	71208 KB	Output is correct
20	Correct	709 ms	71196 KB	Output is correct
21	Correct	692 ms	71156 KB	Output is correct

Subtask #5

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	333 ms	62416 KB	Output is correct
2	Correct	88 ms	844 KB	Output is correct
3	Correct	87 ms	952 KB	Output is correct
4	Correct	75 ms	904 KB	Output is correct
5	Correct	81 ms	1012 KB	Output is correct
6	Correct	88 ms	912 KB	Output is correct
7	Correct	88 ms	912 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	437 ms	62248 KB	Output is correct
12	Correct	318 ms	62640 KB	Output is correct
13	Correct	412 ms	62248 KB	Output is correct
14	Correct	430 ms	62248 KB	Output is correct
15	Correct	306 ms	62400 KB	Output is correct
16	Correct	448 ms	62924 KB	Output is correct
17	Correct	469 ms	62748 KB	Output is correct
18	Correct	422 ms	62912 KB	Output is correct
19	Correct	323 ms	62156 KB	Output is correct
20	Correct	363 ms	62236 KB	Output is correct
21	Correct	350 ms	62140 KB	Output is correct
22	Correct	825 ms	61800 KB	Output is correct
23	Correct	132 ms	716 KB	Output is correct
24	Correct	124 ms	676 KB	Output is correct
25	Correct	136 ms	724 KB	Output is correct
26	Correct	140 ms	612 KB	Output is correct
27	Correct	125 ms	640 KB	Output is correct
28	Correct	129 ms	716 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	328 KB	Output is correct
32	Correct	823 ms	61852 KB	Output is correct
33	Correct	761 ms	61732 KB	Output is correct
34	Correct	869 ms	61916 KB	Output is correct
35	Correct	853 ms	61988 KB	Output is correct
36	Correct	658 ms	62032 KB	Output is correct
37	Correct	635 ms	62060 KB	Output is correct
38	Correct	681 ms	62152 KB	Output is correct
39	Correct	774 ms	61884 KB	Output is correct
40	Correct	863 ms	61928 KB	Output is correct
41	Correct	833 ms	61916 KB	Output is correct
42	Correct	819 ms	61892 KB	Output is correct
43	Correct	776 ms	61908 KB	Output is correct
44	Correct	765 ms	61872 KB	Output is correct
45	Correct	779 ms	61836 KB	Output is correct

Subtask #6

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	169 ms	62028 KB	Output is correct
2	Correct	80 ms	544 KB	Output is correct
3	Correct	82 ms	508 KB	Output is correct
4	Correct	93 ms	608 KB	Output is correct
5	Correct	109 ms	648 KB	Output is correct
6	Correct	80 ms	588 KB	Output is correct
7	Correct	74 ms	588 KB	Output is correct
8	Correct	1 ms	324 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	169 ms	61996 KB	Output is correct
12	Correct	167 ms	61900 KB	Output is correct
13	Correct	153 ms	62256 KB	Output is correct
14	Correct	176 ms	62416 KB	Output is correct
15	Correct	165 ms	62264 KB	Output is correct
16	Correct	195 ms	61984 KB	Output is correct
17	Correct	169 ms	62060 KB	Output is correct
18	Correct	158 ms	61984 KB	Output is correct
19	Incorrect	2 ms	468 KB	Output isn't correct
20	Halted	0 ms	0 KB	-