Submission #538191

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
538191	2022-03-16T07:44:57 Z	blue	Progression (NOI20_progression)	C++17	68 / 100	1275 ms	68512 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;
			
			v = combine(left->v, right->v);
		}
	}
 
	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(N > 1000 || Q > 1000)
				// {
				// 	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	164 ms	62500 KB	Output is correct
2	Correct	78 ms	1504 KB	Output is correct
3	Correct	77 ms	1520 KB	Output is correct
4	Correct	77 ms	1520 KB	Output is correct
5	Correct	79 ms	1536 KB	Output is correct
6	Correct	83 ms	1664 KB	Output is correct
7	Correct	74 ms	1484 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	168 ms	68232 KB	Output is correct
12	Correct	158 ms	68156 KB	Output is correct
13	Correct	182 ms	68420 KB	Output is correct
14	Correct	162 ms	68500 KB	Output is correct
15	Correct	165 ms	68512 KB	Output is correct
16	Correct	161 ms	68084 KB	Output is correct
17	Correct	182 ms	68180 KB	Output is correct
18	Correct	179 ms	68048 KB	Output is correct

Subtask #2

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	468 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	393 ms	62912 KB	Output is correct
2	Correct	91 ms	1744 KB	Output is correct
3	Correct	87 ms	1804 KB	Output is correct
4	Correct	81 ms	1880 KB	Output is correct
5	Correct	87 ms	1892 KB	Output is correct
6	Correct	88 ms	1876 KB	Output is correct
7	Correct	91 ms	1912 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	408 ms	63496 KB	Output is correct
12	Correct	368 ms	66624 KB	Output is correct
13	Correct	494 ms	65412 KB	Output is correct
14	Correct	456 ms	65336 KB	Output is correct
15	Correct	404 ms	66636 KB	Output is correct
16	Correct	531 ms	67236 KB	Output is correct
17	Correct	476 ms	67172 KB	Output is correct
18	Correct	507 ms	67300 KB	Output is correct
19	Correct	461 ms	66616 KB	Output is correct
20	Correct	423 ms	66576 KB	Output is correct
21	Correct	406 ms	66596 KB	Output is correct

Subtask #4

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	861 ms	62228 KB	Output is correct
2	Correct	164 ms	1436 KB	Output is correct
3	Correct	197 ms	1396 KB	Output is correct
4	Correct	221 ms	1332 KB	Output is correct
5	Correct	191 ms	1356 KB	Output is correct
6	Correct	200 ms	1444 KB	Output is correct
7	Correct	196 ms	1372 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	902 ms	62764 KB	Output is correct
12	Correct	993 ms	62736 KB	Output is correct
13	Correct	887 ms	62760 KB	Output is correct
14	Correct	925 ms	62740 KB	Output is correct
15	Correct	822 ms	62812 KB	Output is correct
16	Correct	906 ms	62644 KB	Output is correct
17	Correct	973 ms	62728 KB	Output is correct
18	Correct	1031 ms	62764 KB	Output is correct
19	Correct	809 ms	62700 KB	Output is correct
20	Correct	811 ms	62708 KB	Output is correct
21	Correct	857 ms	62632 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	393 ms	62912 KB	Output is correct
2	Correct	91 ms	1744 KB	Output is correct
3	Correct	87 ms	1804 KB	Output is correct
4	Correct	81 ms	1880 KB	Output is correct
5	Correct	87 ms	1892 KB	Output is correct
6	Correct	88 ms	1876 KB	Output is correct
7	Correct	91 ms	1912 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	408 ms	63496 KB	Output is correct
12	Correct	368 ms	66624 KB	Output is correct
13	Correct	494 ms	65412 KB	Output is correct
14	Correct	456 ms	65336 KB	Output is correct
15	Correct	404 ms	66636 KB	Output is correct
16	Correct	531 ms	67236 KB	Output is correct
17	Correct	476 ms	67172 KB	Output is correct
18	Correct	507 ms	67300 KB	Output is correct
19	Correct	461 ms	66616 KB	Output is correct
20	Correct	423 ms	66576 KB	Output is correct
21	Correct	406 ms	66596 KB	Output is correct
22	Correct	1041 ms	62684 KB	Output is correct
23	Correct	164 ms	1456 KB	Output is correct
24	Correct	168 ms	1460 KB	Output is correct
25	Correct	153 ms	1436 KB	Output is correct
26	Correct	161 ms	1388 KB	Output is correct
27	Correct	194 ms	1568 KB	Output is correct
28	Correct	159 ms	1420 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1088 ms	62660 KB	Output is correct
33	Correct	989 ms	62520 KB	Output is correct
34	Correct	1078 ms	62676 KB	Output is correct
35	Correct	1188 ms	62628 KB	Output is correct
36	Correct	943 ms	62860 KB	Output is correct
37	Correct	880 ms	62868 KB	Output is correct
38	Correct	906 ms	62852 KB	Output is correct
39	Correct	1130 ms	62568 KB	Output is correct
40	Correct	1188 ms	62676 KB	Output is correct
41	Correct	1275 ms	62616 KB	Output is correct
42	Correct	1132 ms	62740 KB	Output is correct
43	Correct	1047 ms	62496 KB	Output is correct
44	Correct	1006 ms	62412 KB	Output is correct
45	Correct	1004 ms	62300 KB	Output is correct

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	164 ms	62500 KB	Output is correct
2	Correct	78 ms	1504 KB	Output is correct
3	Correct	77 ms	1520 KB	Output is correct
4	Correct	77 ms	1520 KB	Output is correct
5	Correct	79 ms	1536 KB	Output is correct
6	Correct	83 ms	1664 KB	Output is correct
7	Correct	74 ms	1484 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	168 ms	68232 KB	Output is correct
12	Correct	158 ms	68156 KB	Output is correct
13	Correct	182 ms	68420 KB	Output is correct
14	Correct	162 ms	68500 KB	Output is correct
15	Correct	165 ms	68512 KB	Output is correct
16	Correct	161 ms	68084 KB	Output is correct
17	Correct	182 ms	68180 KB	Output is correct
18	Correct	179 ms	68048 KB	Output is correct
19	Incorrect	2 ms	468 KB	Output isn't correct
20	Halted	0 ms	0 KB	-