oj.uz

Submission #538112

# Submission time Handle Problem Language Result Execution time Memory
538112 2022-03-16T05:39:51 Z blue Progression (NOI20_progression) C++17
57 / 100
 1597 ms 72852 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 922 ms 63892 KB Output is correct
2 Correct 82 ms 664 KB Output is correct
3 Correct 75 ms 544 KB Output is correct
4 Correct 78 ms 504 KB Output is correct
5 Correct 83 ms 680 KB Output is correct
6 Correct 79 ms 668 KB Output is correct
7 Correct 76 ms 516 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 332 KB Output is correct
11 Correct 924 ms 71788 KB Output is correct
12 Correct 922 ms 71980 KB Output is correct
13 Correct 908 ms 71272 KB Output is correct
14 Correct 947 ms 71048 KB Output is correct
15 Correct 902 ms 71092 KB Output is correct
16 Correct 911 ms 72092 KB Output is correct
17 Correct 909 ms 72192 KB Output is correct
18 Correct 948 ms 72196 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 1136 ms 64060 KB Output is correct
2 Correct 83 ms 960 KB Output is correct
3 Correct 79 ms 844 KB Output is correct
4 Correct 77 ms 904 KB Output is correct
5 Correct 93 ms 892 KB Output is correct
6 Correct 106 ms 1008 KB Output is correct
7 Correct 87 ms 924 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 1138 ms 62920 KB Output is correct
12 Correct 1163 ms 70220 KB Output is correct
13 Correct 1149 ms 67836 KB Output is correct
14 Correct 1169 ms 67804 KB Output is correct
15 Correct 1056 ms 70176 KB Output is correct
16 Correct 1145 ms 69952 KB Output is correct
17 Correct 1135 ms 70032 KB Output is correct
18 Correct 1124 ms 69732 KB Output is correct
19 Correct 1074 ms 70584 KB Output is correct
20 Correct 1065 ms 70636 KB Output is correct
21 Correct 1062 ms 70532 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1381 ms 63200 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 1136 ms 64060 KB Output is correct
2 Correct 83 ms 960 KB Output is correct
3 Correct 79 ms 844 KB Output is correct
4 Correct 77 ms 904 KB Output is correct
5 Correct 93 ms 892 KB Output is correct
6 Correct 106 ms 1008 KB Output is correct
7 Correct 87 ms 924 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 1138 ms 62920 KB Output is correct
12 Correct 1163 ms 70220 KB Output is correct
13 Correct 1149 ms 67836 KB Output is correct
14 Correct 1169 ms 67804 KB Output is correct
15 Correct 1056 ms 70176 KB Output is correct
16 Correct 1145 ms 69952 KB Output is correct
17 Correct 1135 ms 70032 KB Output is correct
18 Correct 1124 ms 69732 KB Output is correct
19 Correct 1074 ms 70584 KB Output is correct
20 Correct 1065 ms 70636 KB Output is correct
21 Correct 1062 ms 70532 KB Output is correct
22 Correct 1530 ms 72372 KB Output is correct
23 Correct 143 ms 3664 KB Output is correct
24 Correct 136 ms 3460 KB Output is correct
25 Correct 135 ms 3524 KB Output is correct
26 Correct 128 ms 3460 KB Output is correct
27 Correct 142 ms 3556 KB Output is correct
28 Correct 176 ms 3572 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 336 KB Output is correct
32 Correct 1559 ms 68636 KB Output is correct
33 Correct 1546 ms 72636 KB Output is correct
34 Correct 1556 ms 68492 KB Output is correct
35 Correct 1583 ms 68516 KB Output is correct
36 Correct 1412 ms 68444 KB Output is correct
37 Correct 1414 ms 68492 KB Output is correct
38 Correct 1382 ms 68408 KB Output is correct
39 Correct 1512 ms 72464 KB Output is correct
40 Correct 1536 ms 71764 KB Output is correct
41 Correct 1584 ms 71652 KB Output is correct
42 Correct 1540 ms 71540 KB Output is correct
43 Correct 1551 ms 72760 KB Output is correct
44 Correct 1597 ms 72852 KB Output is correct
45 Correct 1516 ms 72852 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 63892 KB Output is correct
2 Correct 82 ms 664 KB Output is correct
3 Correct 75 ms 544 KB Output is correct
4 Correct 78 ms 504 KB Output is correct
5 Correct 83 ms 680 KB Output is correct
6 Correct 79 ms 668 KB Output is correct
7 Correct 76 ms 516 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 332 KB Output is correct
11 Correct 924 ms 71788 KB Output is correct
12 Correct 922 ms 71980 KB Output is correct
13 Correct 908 ms 71272 KB Output is correct
14 Correct 947 ms 71048 KB Output is correct
15 Correct 902 ms 71092 KB Output is correct
16 Correct 911 ms 72092 KB Output is correct
17 Correct 909 ms 72192 KB Output is correct
18 Correct 948 ms 72196 KB Output is correct
19 Incorrect 4 ms 468 KB Output isn't correct
20 Halted 0 ms 0 KB -