oj.uz

Submission #538122

# Submission time Handle Problem Language Result Execution time Memory
538122 2022-03-16T06:00:04 Z blue Progression (NOI20_progression) C++17
57 / 100
 3000 ms 70592 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 1120 ms 65380 KB Output is correct
2 Correct 1068 ms 3464 KB Output is correct
3 Correct 1059 ms 3456 KB Output is correct
4 Correct 1014 ms 3612 KB Output is correct
5 Correct 1049 ms 3860 KB Output is correct
6 Correct 1032 ms 3740 KB Output is correct
7 Correct 1062 ms 3516 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 328 KB Output is correct
11 Correct 1164 ms 65632 KB Output is correct
12 Correct 1165 ms 65624 KB Output is correct
13 Correct 1117 ms 66036 KB Output is correct
14 Correct 1151 ms 66140 KB Output is correct
15 Correct 1109 ms 65992 KB Output is correct
16 Correct 1110 ms 65620 KB Output is correct
17 Correct 1118 ms 65632 KB Output is correct
18 Correct 1172 ms 65732 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 568 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 1077 ms 64248 KB Output is correct
2 Correct 847 ms 2876 KB Output is correct
3 Correct 837 ms 2972 KB Output is correct
4 Correct 811 ms 2956 KB Output is correct
5 Correct 854 ms 2920 KB Output is correct
6 Correct 831 ms 2832 KB Output is correct
7 Correct 854 ms 2892 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1189 ms 64152 KB Output is correct
12 Correct 1057 ms 64876 KB Output is correct
13 Correct 1269 ms 64388 KB Output is correct
14 Correct 1262 ms 64360 KB Output is correct
15 Correct 1238 ms 64644 KB Output is correct
16 Correct 1292 ms 65076 KB Output is correct
17 Correct 1290 ms 64928 KB Output is correct
18 Correct 1281 ms 65104 KB Output is correct
19 Correct 1255 ms 64308 KB Output is correct
20 Correct 1166 ms 64236 KB Output is correct
21 Correct 1297 ms 64324 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 70592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 64248 KB Output is correct
2 Correct 847 ms 2876 KB Output is correct
3 Correct 837 ms 2972 KB Output is correct
4 Correct 811 ms 2956 KB Output is correct
5 Correct 854 ms 2920 KB Output is correct
6 Correct 831 ms 2832 KB Output is correct
7 Correct 854 ms 2892 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1189 ms 64152 KB Output is correct
12 Correct 1057 ms 64876 KB Output is correct
13 Correct 1269 ms 64388 KB Output is correct
14 Correct 1262 ms 64360 KB Output is correct
15 Correct 1238 ms 64644 KB Output is correct
16 Correct 1292 ms 65076 KB Output is correct
17 Correct 1290 ms 64928 KB Output is correct
18 Correct 1281 ms 65104 KB Output is correct
19 Correct 1255 ms 64308 KB Output is correct
20 Correct 1166 ms 64236 KB Output is correct
21 Correct 1297 ms 64324 KB Output is correct
22 Correct 1519 ms 64016 KB Output is correct
23 Correct 761 ms 2752 KB Output is correct
24 Correct 751 ms 2848 KB Output is correct
25 Correct 751 ms 2884 KB Output is correct
26 Correct 757 ms 2784 KB Output is correct
27 Correct 754 ms 2932 KB Output is correct
28 Correct 783 ms 2784 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 1579 ms 63936 KB Output is correct
33 Correct 1465 ms 64004 KB Output is correct
34 Correct 1532 ms 64056 KB Output is correct
35 Correct 1512 ms 64204 KB Output is correct
36 Correct 1493 ms 64252 KB Output is correct
37 Correct 1412 ms 64412 KB Output is correct
38 Correct 1437 ms 64376 KB Output is correct
39 Correct 1462 ms 63952 KB Output is correct
40 Correct 1517 ms 64008 KB Output is correct
41 Correct 1534 ms 64040 KB Output is correct
42 Correct 1611 ms 64000 KB Output is correct
43 Correct 1481 ms 63972 KB Output is correct
44 Correct 1472 ms 64080 KB Output is correct
45 Correct 1508 ms 63804 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1120 ms 65380 KB Output is correct
2 Correct 1068 ms 3464 KB Output is correct
3 Correct 1059 ms 3456 KB Output is correct
4 Correct 1014 ms 3612 KB Output is correct
5 Correct 1049 ms 3860 KB Output is correct
6 Correct 1032 ms 3740 KB Output is correct
7 Correct 1062 ms 3516 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 328 KB Output is correct
11 Correct 1164 ms 65632 KB Output is correct
12 Correct 1165 ms 65624 KB Output is correct
13 Correct 1117 ms 66036 KB Output is correct
14 Correct 1151 ms 66140 KB Output is correct
15 Correct 1109 ms 65992 KB Output is correct
16 Correct 1110 ms 65620 KB Output is correct
17 Correct 1118 ms 65632 KB Output is correct
18 Correct 1172 ms 65732 KB Output is correct
19 Incorrect 15 ms 568 KB Output isn't correct
20 Halted 0 ms 0 KB -