oj.uz

Submission #538123

# Submission time Handle Problem Language Result Execution time Memory
538123 2022-03-16T06:00:36 Z blue Progression (NOI20_progression) C++17
57 / 100
 1836 ms 65024 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;

			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';
			}

			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));
			}

			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

# Verdict Execution time Memory Grader output
1 Correct 769 ms 63836 KB Output is correct
2 Correct 696 ms 2532 KB Output is correct
3 Correct 707 ms 2388 KB Output is correct
4 Correct 664 ms 2296 KB Output is correct
5 Correct 663 ms 2408 KB Output is correct
6 Correct 678 ms 2380 KB Output is correct
7 Correct 700 ms 2388 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 756 ms 63812 KB Output is correct
12 Correct 763 ms 63692 KB Output is correct
13 Correct 762 ms 64016 KB Output is correct
14 Correct 771 ms 64052 KB Output is correct
15 Correct 733 ms 63944 KB Output is correct
16 Correct 777 ms 63720 KB Output is correct
17 Correct 745 ms 63860 KB Output is correct
18 Correct 772 ms 63728 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 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 1162 ms 64268 KB Output is correct
2 Correct 881 ms 2660 KB Output is correct
3 Correct 901 ms 2916 KB Output is correct
4 Correct 891 ms 2632 KB Output is correct
5 Correct 908 ms 2800 KB Output is correct
6 Correct 893 ms 2688 KB Output is correct
7 Correct 887 ms 2748 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 1349 ms 63924 KB Output is correct
12 Correct 1149 ms 64276 KB Output is correct
13 Correct 1274 ms 63968 KB Output is correct
14 Correct 1235 ms 64012 KB Output is correct
15 Correct 1146 ms 64176 KB Output is correct
16 Correct 1267 ms 64552 KB Output is correct
17 Correct 1219 ms 64568 KB Output is correct
18 Correct 1241 ms 64612 KB Output is correct
19 Correct 1148 ms 63944 KB Output is correct
20 Correct 1138 ms 63828 KB Output is correct
21 Correct 1128 ms 63836 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1162 ms 64268 KB Output is correct
2 Correct 881 ms 2660 KB Output is correct
3 Correct 901 ms 2916 KB Output is correct
4 Correct 891 ms 2632 KB Output is correct
5 Correct 908 ms 2800 KB Output is correct
6 Correct 893 ms 2688 KB Output is correct
7 Correct 887 ms 2748 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 1349 ms 63924 KB Output is correct
12 Correct 1149 ms 64276 KB Output is correct
13 Correct 1274 ms 63968 KB Output is correct
14 Correct 1235 ms 64012 KB Output is correct
15 Correct 1146 ms 64176 KB Output is correct
16 Correct 1267 ms 64552 KB Output is correct
17 Correct 1219 ms 64568 KB Output is correct
18 Correct 1241 ms 64612 KB Output is correct
19 Correct 1148 ms 63944 KB Output is correct
20 Correct 1138 ms 63828 KB Output is correct
21 Correct 1128 ms 63836 KB Output is correct
22 Correct 1508 ms 63452 KB Output is correct
23 Correct 729 ms 2308 KB Output is correct
24 Correct 721 ms 2324 KB Output is correct
25 Correct 741 ms 2296 KB Output is correct
26 Correct 719 ms 2336 KB Output is correct
27 Correct 730 ms 2452 KB Output is correct
28 Correct 725 ms 2436 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 1389 ms 63604 KB Output is correct
33 Correct 1293 ms 63612 KB Output is correct
34 Correct 1345 ms 63620 KB Output is correct
35 Correct 1334 ms 63816 KB Output is correct
36 Correct 1322 ms 63960 KB Output is correct
37 Correct 1262 ms 63948 KB Output is correct
38 Correct 1264 ms 63824 KB Output is correct
39 Correct 1291 ms 63576 KB Output is correct
40 Correct 1399 ms 63760 KB Output is correct
41 Correct 1399 ms 63644 KB Output is correct
42 Correct 1426 ms 63648 KB Output is correct
43 Correct 1284 ms 63644 KB Output is correct
44 Correct 1328 ms 63596 KB Output is correct
45 Correct 1326 ms 63596 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 769 ms 63836 KB Output is correct
2 Correct 696 ms 2532 KB Output is correct
3 Correct 707 ms 2388 KB Output is correct
4 Correct 664 ms 2296 KB Output is correct
5 Correct 663 ms 2408 KB Output is correct
6 Correct 678 ms 2380 KB Output is correct
7 Correct 700 ms 2388 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 756 ms 63812 KB Output is correct
12 Correct 763 ms 63692 KB Output is correct
13 Correct 762 ms 64016 KB Output is correct
14 Correct 771 ms 64052 KB Output is correct
15 Correct 733 ms 63944 KB Output is correct
16 Correct 777 ms 63720 KB Output is correct
17 Correct 745 ms 63860 KB Output is correct
18 Correct 772 ms 63728 KB Output is correct
19 Incorrect 6 ms 468 KB Output isn't correct
20 Halted 0 ms 0 KB -