oj.uz

Submission #538113

# Submission time Handle Problem Language Result Execution time Memory
538113 2022-03-16T05:42:45 Z blue Progression (NOI20_progression) C++17
57 / 100
 867 ms 63456 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";

	for(int j = 1; j <= Q; j++)
	{
		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);
		}
		else if(o == 2)
		{
			ll L, R, S, C;
			cin >> L >> R >> S >> C;
			// S -= adj;

			if(L > 1)
			{
				ST.rangeset(L-1, L-1, S - 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';
				ST.rangeadd(R, R, ST.rangesum(1, R-1) - (S + (R-L)*C));
			}

			if(L < R)
				ST.rangeset(L, R-1, C);
		}
		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 211 ms 61952 KB Output is correct
2 Correct 75 ms 540 KB Output is correct
3 Correct 80 ms 584 KB Output is correct
4 Correct 95 ms 584 KB Output is correct
5 Correct 88 ms 628 KB Output is correct
6 Correct 75 ms 672 KB Output is correct
7 Correct 75 ms 588 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 188 ms 62508 KB Output is correct
12 Correct 173 ms 62492 KB Output is correct
13 Correct 171 ms 62724 KB Output is correct
14 Correct 166 ms 62900 KB Output is correct
15 Correct 165 ms 62832 KB Output is correct
16 Correct 172 ms 62452 KB Output is correct
17 Correct 181 ms 62540 KB Output is correct
18 Correct 168 ms 62548 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 326 ms 62368 KB Output is correct
2 Correct 95 ms 864 KB Output is correct
3 Correct 84 ms 844 KB Output is correct
4 Correct 72 ms 784 KB Output is correct
5 Correct 86 ms 972 KB Output is correct
6 Correct 115 ms 1124 KB Output is correct
7 Correct 85 ms 900 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 390 ms 62180 KB Output is correct
12 Correct 317 ms 63028 KB Output is correct
13 Correct 418 ms 62780 KB Output is correct
14 Correct 382 ms 62752 KB Output is correct
15 Correct 362 ms 63020 KB Output is correct
16 Correct 410 ms 63304 KB Output is correct
17 Correct 402 ms 63308 KB Output is correct
18 Correct 471 ms 63456 KB Output is correct
19 Correct 314 ms 62572 KB Output is correct
20 Correct 382 ms 62584 KB Output is correct
21 Correct 334 ms 62540 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 671 ms 61556 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 326 ms 62368 KB Output is correct
2 Correct 95 ms 864 KB Output is correct
3 Correct 84 ms 844 KB Output is correct
4 Correct 72 ms 784 KB Output is correct
5 Correct 86 ms 972 KB Output is correct
6 Correct 115 ms 1124 KB Output is correct
7 Correct 85 ms 900 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 390 ms 62180 KB Output is correct
12 Correct 317 ms 63028 KB Output is correct
13 Correct 418 ms 62780 KB Output is correct
14 Correct 382 ms 62752 KB Output is correct
15 Correct 362 ms 63020 KB Output is correct
16 Correct 410 ms 63304 KB Output is correct
17 Correct 402 ms 63308 KB Output is correct
18 Correct 471 ms 63456 KB Output is correct
19 Correct 314 ms 62572 KB Output is correct
20 Correct 382 ms 62584 KB Output is correct
21 Correct 334 ms 62540 KB Output is correct
22 Correct 841 ms 62276 KB Output is correct
23 Correct 145 ms 1100 KB Output is correct
24 Correct 136 ms 1280 KB Output is correct
25 Correct 143 ms 1096 KB Output is correct
26 Correct 140 ms 1076 KB Output is correct
27 Correct 132 ms 1100 KB Output is correct
28 Correct 147 ms 1168 KB Output is correct
29 Correct 1 ms 224 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 841 ms 62380 KB Output is correct
33 Correct 817 ms 62316 KB Output is correct
34 Correct 858 ms 62224 KB Output is correct
35 Correct 844 ms 62360 KB Output is correct
36 Correct 687 ms 62388 KB Output is correct
37 Correct 681 ms 62308 KB Output is correct
38 Correct 637 ms 62404 KB Output is correct
39 Correct 783 ms 62112 KB Output is correct
40 Correct 861 ms 62256 KB Output is correct
41 Correct 860 ms 62140 KB Output is correct
42 Correct 867 ms 61872 KB Output is correct
43 Correct 775 ms 61752 KB Output is correct
44 Correct 824 ms 61720 KB Output is correct
45 Correct 843 ms 61732 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 61952 KB Output is correct
2 Correct 75 ms 540 KB Output is correct
3 Correct 80 ms 584 KB Output is correct
4 Correct 95 ms 584 KB Output is correct
5 Correct 88 ms 628 KB Output is correct
6 Correct 75 ms 672 KB Output is correct
7 Correct 75 ms 588 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 188 ms 62508 KB Output is correct
12 Correct 173 ms 62492 KB Output is correct
13 Correct 171 ms 62724 KB Output is correct
14 Correct 166 ms 62900 KB Output is correct
15 Correct 165 ms 62832 KB Output is correct
16 Correct 172 ms 62452 KB Output is correct
17 Correct 181 ms 62540 KB Output is correct
18 Correct 168 ms 62548 KB Output is correct
19 Incorrect 2 ms 468 KB Output isn't correct
20 Halted 0 ms 0 KB -