oj.uz

답안 #660276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660276 2022-11-21T12:58:43 Z franfill Growing Trees (BOI11_grow) C++17
0 / 100
 338 ms 5036 KB 
#include<bits/stdc++.h>
using namespace std;

struct segtree
{
	struct node
	{
		int max;
		int lazy = 0;
		node(int v) : max(v)
		{
		}
		node() : max(-1)
		{
		}
	};

	void merge(node &c, node a, node b)
	{
		c.max = max(a.max, b.max);
	}
	int n;
	int w;
	vector < node > T;

	segtree(vector < int > V)
	{
		w = V.size();
		for (n = 1; n < V.size(); n *= 2);
		T.resize(n*2);
		for (int i = 0; i < V.size(); i++)
			T[n+i] = node(V[i]);
		for (int k = n-1; k; k--)
			merge(T[k], T[k*2], T[k*2+1]);
	}

	void propagate(int k)
	{
		T[k].max += T[k].lazy;
		if (k < n)
		{
			T[k*2].lazy += T[k].lazy;
			T[k*2+1].lazy += T[k].lazy;
		}
		T[k].lazy = 0;
	}

	void add(int l, int r, int k=1, int x=0, int y=-1)
	{
		if (y == -1)
			y = n;
		if (l <= x && y <= r)
			T[k].lazy++;
		propagate(k);
		if (l <= x && y <= r)
			return;
		if (r <= x || y <= l)
			return;
		int m = (x+y)/2;
		add(l, r, k*2, x, m);
		add(l, r, k*2+1, m, y);
		merge(T[k], T[k*2], T[k*2+1]);
	}

	int right_bound(int l, int r, int h, int k=1, int x=0, int y=-1)
	{
		if (y == -1)
			y = n;
		propagate(k);
		if (r <= x || y <= l)
			return w;
		if (T[k].max < h)
			return w;
		if (x == y-1)
			return x;
		int m = (x+y)/2;
		int ans = right_bound(l, r, h, k*2, x, m);
		if (ans == w)
			ans = right_bound(l, r, h, k*2+1, m, y);
		return ans;
	}
};

int main()
{
	int N, M;	
	cin >> N >> M;
	vector < int > H(N);
	for (int &h : H)
		cin >> h;
	sort(H.begin(), H.end());
	segtree seg(H);
	for (int m = 0; m < M; m++)
	{
		char t;
		cin >> t;
		if (t == 'F')
		{
			int c, h;
			cin>> c >> h;
			int i = seg.right_bound(0, N, h);
			int l = h, r = (M+N)+1;
			while(l < r-1)
			{
				int m = (l+r)/2;
				int j = seg.right_bound(i, N, m);
				if ((j-i) <= c)
					l = m;
				else
					r = m;
			}
			int j1 = seg.right_bound(i, N, l);
			int j2 = seg.right_bound(i, N, r);
			int leftover = c - (j1 - i);
			seg.add(i, j1);
			seg.add(j2-leftover, j2);
		}
		else
		{
			int mi, ma;
			cin >> mi >> ma;
			int i = seg.right_bound(0, N, mi);
			int j = seg.right_bound(0, N, ma+1);
			cout << j-i << "\n";
		}
	}
}

Compilation message

grow.cpp: In constructor 'segtree::segtree(std::vector<int>)':
grow.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (n = 1; n < V.size(); n *= 2);
      |               ~~^~~~~~~~~~
grow.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (int i = 0; i < V.size(); i++)
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 180 ms 3924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Incorrect 8 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 181 ms 1664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 215 ms 1716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 171 ms 2660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 204 ms 3708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 180 ms 3744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 338 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 221 ms 4104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 245 ms 5036 KB Output isn't correct
2 Halted 0 ms 0 KB -