oj.uz

답안 #538155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
538155 2022-03-16T06:34:19 Z blue Progression (NOI20_progression) C++17
0 / 100
 3000 ms 70188 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);
			// ll SPL = ST.rangesum(1, L-2);

			ll elementR = ST.rangesum(1, R-1) + A0;

			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, (SR - SPL));
				ST.rangeadd(R, R, -(S + (R-L)*C - elementR));
			}

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

		cerr << "array : ";
		for(int i = 1; i <= N; i++) cerr << A0 + ST.rangesum(1, i-1) << ' ';
			cerr << '\n';
		cerr << "differences : ";
		cerr << A0 << "  " ;
		for(int i = 1; i < N; i++) cerr << ST.rangesum(i, i) << ' ';
			cerr << '\n';

		cerr << "\n\n";
	}
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3047 ms 70188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3079 ms 10792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3075 ms 69956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3063 ms 69408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3075 ms 69956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3047 ms 70188 KB Time limit exceeded
2 Halted 0 ms 0 KB -