Submission #538180

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
538180	2022-03-16T07:34:08 Z	blue	Progression (NOI20_progression)	C++17	68 / 100	911 ms	64424 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);
			// ll SPL = ST.rangesum(1, L-2);
 
			ll elementR = ST.rangesum(1, R-1) + A0;
 
			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, (SR - SPL));
				ST.rangeadd(R, R, -(S + (R-L)*C - elementR));
			}
 
			if(L < R)
			{
				// cerr << "ST range set " << L << ' ' << R-1 << ' ' << C << '\n';
				// ST.rangeset(L, R-1, C);

				if(L == 1 && R == N)
				{
					ST.rangeset(L, R-1, C);
				}
				else
				{
					for(int f = L; f <= R-1; f++)
						ST.rangeadd(f, f, C - ST.rangesum(f, f));	
				}

				
			}
 
			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

#	Verdict	Execution time	Memory	Grader output
1	Correct	158 ms	62028 KB	Output is correct
2	Correct	96 ms	1680 KB	Output is correct
3	Correct	77 ms	1748 KB	Output is correct
4	Correct	92 ms	1728 KB	Output is correct
5	Correct	92 ms	1740 KB	Output is correct
6	Correct	80 ms	1832 KB	Output is correct
7	Correct	84 ms	1740 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	332 KB	Output is correct
11	Correct	166 ms	64212 KB	Output is correct
12	Correct	179 ms	64056 KB	Output is correct
13	Correct	169 ms	64424 KB	Output is correct
14	Correct	208 ms	64368 KB	Output is correct
15	Correct	163 ms	64392 KB	Output is correct
16	Correct	174 ms	64088 KB	Output is correct
17	Correct	166 ms	64116 KB	Output is correct
18	Correct	171 ms	64104 KB	Output is correct

Subtask #2

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	524 KB	Output is correct
2	Correct	2 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Incorrect	1 ms	320 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	326 ms	62380 KB	Output is correct
2	Correct	84 ms	972 KB	Output is correct
3	Correct	80 ms	1084 KB	Output is correct
4	Correct	69 ms	920 KB	Output is correct
5	Correct	79 ms	1064 KB	Output is correct
6	Correct	83 ms	1008 KB	Output is correct
7	Correct	81 ms	972 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	371 ms	62276 KB	Output is correct
12	Correct	301 ms	62540 KB	Output is correct
13	Correct	384 ms	62096 KB	Output is correct
14	Correct	371 ms	62208 KB	Output is correct
15	Correct	293 ms	62400 KB	Output is correct
16	Correct	376 ms	62796 KB	Output is correct
17	Correct	379 ms	62736 KB	Output is correct
18	Correct	389 ms	62888 KB	Output is correct
19	Correct	342 ms	62108 KB	Output is correct
20	Correct	329 ms	62156 KB	Output is correct
21	Correct	315 ms	62028 KB	Output is correct

Subtask #4

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	638 ms	61812 KB	Output is correct
2	Correct	127 ms	588 KB	Output is correct
3	Correct	130 ms	532 KB	Output is correct
4	Correct	123 ms	576 KB	Output is correct
5	Correct	134 ms	484 KB	Output is correct
6	Correct	131 ms	576 KB	Output is correct
7	Correct	134 ms	476 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	619 ms	61632 KB	Output is correct
12	Correct	603 ms	61720 KB	Output is correct
13	Correct	672 ms	61640 KB	Output is correct
14	Correct	636 ms	61704 KB	Output is correct
15	Correct	559 ms	61592 KB	Output is correct
16	Correct	631 ms	61724 KB	Output is correct
17	Correct	630 ms	61812 KB	Output is correct
18	Correct	636 ms	61736 KB	Output is correct
19	Correct	621 ms	61632 KB	Output is correct
20	Correct	630 ms	61900 KB	Output is correct
21	Correct	604 ms	61644 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	326 ms	62380 KB	Output is correct
2	Correct	84 ms	972 KB	Output is correct
3	Correct	80 ms	1084 KB	Output is correct
4	Correct	69 ms	920 KB	Output is correct
5	Correct	79 ms	1064 KB	Output is correct
6	Correct	83 ms	1008 KB	Output is correct
7	Correct	81 ms	972 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	371 ms	62276 KB	Output is correct
12	Correct	301 ms	62540 KB	Output is correct
13	Correct	384 ms	62096 KB	Output is correct
14	Correct	371 ms	62208 KB	Output is correct
15	Correct	293 ms	62400 KB	Output is correct
16	Correct	376 ms	62796 KB	Output is correct
17	Correct	379 ms	62736 KB	Output is correct
18	Correct	389 ms	62888 KB	Output is correct
19	Correct	342 ms	62108 KB	Output is correct
20	Correct	329 ms	62156 KB	Output is correct
21	Correct	315 ms	62028 KB	Output is correct
22	Correct	737 ms	61732 KB	Output is correct
23	Correct	124 ms	624 KB	Output is correct
24	Correct	128 ms	576 KB	Output is correct
25	Correct	125 ms	600 KB	Output is correct
26	Correct	132 ms	692 KB	Output is correct
27	Correct	128 ms	564 KB	Output is correct
28	Correct	128 ms	616 KB	Output is correct
29	Correct	1 ms	328 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	751 ms	61960 KB	Output is correct
33	Correct	707 ms	62104 KB	Output is correct
34	Correct	771 ms	61772 KB	Output is correct
35	Correct	858 ms	61872 KB	Output is correct
36	Correct	670 ms	62028 KB	Output is correct
37	Correct	681 ms	62076 KB	Output is correct
38	Correct	662 ms	62216 KB	Output is correct
39	Correct	821 ms	61872 KB	Output is correct
40	Correct	839 ms	61748 KB	Output is correct
41	Correct	905 ms	61736 KB	Output is correct
42	Correct	911 ms	61836 KB	Output is correct
43	Correct	877 ms	61708 KB	Output is correct
44	Correct	853 ms	61760 KB	Output is correct
45	Correct	815 ms	61708 KB	Output is correct

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	158 ms	62028 KB	Output is correct
2	Correct	96 ms	1680 KB	Output is correct
3	Correct	77 ms	1748 KB	Output is correct
4	Correct	92 ms	1728 KB	Output is correct
5	Correct	92 ms	1740 KB	Output is correct
6	Correct	80 ms	1832 KB	Output is correct
7	Correct	84 ms	1740 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	332 KB	Output is correct
11	Correct	166 ms	64212 KB	Output is correct
12	Correct	179 ms	64056 KB	Output is correct
13	Correct	169 ms	64424 KB	Output is correct
14	Correct	208 ms	64368 KB	Output is correct
15	Correct	163 ms	64392 KB	Output is correct
16	Correct	174 ms	64088 KB	Output is correct
17	Correct	166 ms	64116 KB	Output is correct
18	Correct	171 ms	64104 KB	Output is correct
19	Correct	27 ms	524 KB	Output is correct
20	Correct	2 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Incorrect	1 ms	320 KB	Output isn't correct
23	Halted	0 ms	0 KB	-