oj.uz

Submission #569071

# Submission time Handle Problem Language Result Execution time Memory
569071 2022-05-26T14:58:16 Z blue Fish 2 (JOI22_fish2) C++17
0 / 100
 0 ms 212 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())

int N;
vll A;

int Q;

struct group
{
	int i; //inclusive of the group, not the barrier.
	ll Asum;
	int winners;
};

struct info
{
	int l;
	int r;

	ll Asum;
	int winners;

	vector<group> pref;
	vector<group> suff;

	info()
	{
		;
	}

	info(int i)
	{
		l = r = i;
		Asum = A[i];
		winners = 1;
	}
};

void combine(info& res, const info& A, const info& B) //!
{
	res = A;
}

info combine(const info& A, const info& B)
{
	info res;
	combine(res, A, B);
	return res;
}


struct segtree
{
	info v;
	segtree* left = NULL;
	segtree* right = NULL;

	segtree()
	{
		;
	}

	segtree(int L, int R)
	{
		if(L == R)
			v = info(L);
		else
		{
			left = new segtree(L, (L+R)/2);
			right = new segtree((L+R)/2+1, R);
			combine(v, left->v, right->v);
		}
	}

	void recompute(int I)
	{
		if(v.l == v.r)
			v = info(v.l);
		else
		{
			if(I <= (v.l+v.r)/2)
				left->recompute(I);
			else
				right->recompute(I);

			combine(v, left->v, right->v);
		}
	}

	info range(int L, int R)
	{
		if(L <= v.l && v.r <= R)
			return v;
		else if(R <= (v.l+v.r)/2)
			return left->range(L, R);
		else if(L >= (v.l+v.r)/2+1)
			return right->range(L, R);
		else
			return combine(left->range(L, R), right->range(L, R));
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	A = vll(1+N);
	for(int i = 1; i <= N; i++)
		cin >> A[i];

	// cerr << "done\n";

	segtree S(1, N);

	// cerr << "done2\n";


	cin >> Q;
	for(int j = 1; j <= Q; j++)
	{
		int T;
		cin >> T;

		if(T == 1)
		{
			int X, Y;
			cin >> X >> Y;
			A[X] = Y;
			S.recompute(X);
			// cerr << "hello\n";
		}
		else
		{
			int L, R;
			cin >> L >> R;
			cout << S.range(L, R).winners << '\n';
		}
	}
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 17.0

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