oj.uz

Submission #538127

# Submission time Handle Problem Language Result Execution time Memory
538127 2022-03-16T06:06:53 Z blue Progression (NOI20_progression) C++17
59 / 100
 1018 ms 62848 KB 
#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
0 / 9.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 456 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 335 ms 62372 KB Output is correct
2 Correct 83 ms 972 KB Output is correct
3 Correct 75 ms 920 KB Output is correct
4 Correct 69 ms 936 KB Output is correct
5 Correct 114 ms 1004 KB Output is correct
6 Correct 77 ms 1068 KB Output is correct
7 Correct 82 ms 1072 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 396 ms 62236 KB Output is correct
12 Correct 326 ms 62480 KB Output is correct
13 Correct 382 ms 62156 KB Output is correct
14 Correct 427 ms 62196 KB Output is correct
15 Correct 328 ms 62436 KB Output is correct
16 Correct 495 ms 62808 KB Output is correct
17 Correct 424 ms 62760 KB Output is correct
18 Correct 395 ms 62848 KB Output is correct
19 Correct 353 ms 62136 KB Output is correct
20 Correct 321 ms 62264 KB Output is correct
21 Correct 337 ms 62248 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 61732 KB Output is correct
2 Correct 136 ms 628 KB Output is correct
3 Correct 131 ms 636 KB Output is correct
4 Correct 133 ms 652 KB Output is correct
5 Correct 139 ms 624 KB Output is correct
6 Correct 135 ms 580 KB Output is correct
7 Correct 135 ms 628 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 722 ms 61768 KB Output is correct
12 Correct 679 ms 61856 KB Output is correct
13 Correct 701 ms 61956 KB Output is correct
14 Correct 667 ms 61784 KB Output is correct
15 Correct 693 ms 61692 KB Output is correct
16 Correct 725 ms 61772 KB Output is correct
17 Correct 720 ms 61824 KB Output is correct
18 Correct 763 ms 61836 KB Output is correct
19 Correct 696 ms 61836 KB Output is correct
20 Correct 709 ms 61796 KB Output is correct
21 Correct 737 ms 61764 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 62372 KB Output is correct
2 Correct 83 ms 972 KB Output is correct
3 Correct 75 ms 920 KB Output is correct
4 Correct 69 ms 936 KB Output is correct
5 Correct 114 ms 1004 KB Output is correct
6 Correct 77 ms 1068 KB Output is correct
7 Correct 82 ms 1072 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 396 ms 62236 KB Output is correct
12 Correct 326 ms 62480 KB Output is correct
13 Correct 382 ms 62156 KB Output is correct
14 Correct 427 ms 62196 KB Output is correct
15 Correct 328 ms 62436 KB Output is correct
16 Correct 495 ms 62808 KB Output is correct
17 Correct 424 ms 62760 KB Output is correct
18 Correct 395 ms 62848 KB Output is correct
19 Correct 353 ms 62136 KB Output is correct
20 Correct 321 ms 62264 KB Output is correct
21 Correct 337 ms 62248 KB Output is correct
22 Correct 821 ms 61820 KB Output is correct
23 Correct 145 ms 556 KB Output is correct
24 Correct 134 ms 484 KB Output is correct
25 Correct 122 ms 496 KB Output is correct
26 Correct 141 ms 576 KB Output is correct
27 Correct 144 ms 524 KB Output is correct
28 Correct 159 ms 588 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 878 ms 61924 KB Output is correct
33 Correct 845 ms 61788 KB Output is correct
34 Correct 868 ms 61856 KB Output is correct
35 Correct 1018 ms 61692 KB Output is correct
36 Correct 694 ms 62032 KB Output is correct
37 Correct 702 ms 61988 KB Output is correct
38 Correct 722 ms 62104 KB Output is correct
39 Correct 914 ms 61732 KB Output is correct
40 Correct 915 ms 61804 KB Output is correct
41 Correct 989 ms 61876 KB Output is correct
42 Correct 854 ms 61852 KB Output is correct
43 Correct 788 ms 61744 KB Output is correct
44 Correct 853 ms 61668 KB Output is correct
45 Correct 795 ms 61688 KB Output is correct

Subtask #6
0 / 17.0

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