Submission #590192

#	Time	Username	Problem	Language	Result	Execution time	Memory
590192		franfill	Weirdtree (RMI21_weirdtree)	C++17	0 / 100	2069 ms	26024 KiB

weirdtree

#include "weirdtree.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct segtree
{
	struct node
	{
		int max1=-(1<<30), max2=-(1<<30);
		int max1_cnt = 0;
		int sum=0;
		int tag = 1<<30;
		node(){};
		node(int v)
		{
			sum = v;
			max1_cnt = 1;
			max1 = v;
			max2 = -(1<<30);
		}
		
		void print()
		{
			//cout<<"max1: "<<max1<<" max2: "<<max2<<" sum: "<<sum<<" max1_cnt: "<<max1_cnt<<" tag:"<<tag<<endl;
		}
	};

	vector < node > t;
	int n;
	segtree(vector < int > &v)
	{
		for (n = 1; n < v.size(); n *= 2);
		t.resize(2*n);
		for (int i = 0; i < v.size(); i++) t[i+n] = node(v[i]);
		for (int k = n-1; k; k--) 
		{
			merge(t[k], t[k*2], t[k*2+1]);
		}
		for (int i = 1; i < 2*n; i++)
		{
			//cout << i << ": ";
			//t[i].print();
		}
	}

	void merge(node &c, node a, node b)
	{
		if (a.max1 < b.max1) swap(a, b);

		c.sum = a.sum + b.sum;
		c.max1 = a.max1;
		c.max1_cnt = a.max1_cnt;
		if (b.max1 != a.max1) c.max2 = max(b.max1, a.max2);
		else c.max2 = max(a.max2, b.max2), c.max1_cnt += b.max1_cnt;
	}

	void propagate(int k)
	{
		if (t[k].tag >= t[k].max1) return;
		t[k].sum -= (t[k].max1-t[k].tag)*t[k].max1_cnt;
		t[k].max1 = t[k].tag;
		if (k < n)
		{
			t[k*2].tag = min(t[k*2].tag, t[k].tag);
			t[k*2+1].tag = min(t[k*2+1].tag, t[k].tag);
		}
		t[k].tag = 1<<30;
	}

	void set(int i, int val, int k=1, int x=0, int y=-1)
	{
		if (y == -1) y = n;
		propagate(k);
		if (x == i && y == x + 1) 
		{
			t[k] = node(val);
			return;
		}
		if (y <= i || x > i) return;
		int m = (x+y)/2;
		set(i, val, k*2, x, m);
		set(i, val, k*2+1, m, y);
		merge(t[k], t[k*2], t[k*2+1]);
	}

	int set_min(int l, int r, int v, bool apply, int count, int k=1, int x=0, int y=-1)
	{
		if (y == -1) y = n;
		//cout << k << ": ";
		//t[k].print();

		propagate(k);
		if (v >= t[k].max1) return 0;
		if (y <= l || r <= x) return 0;

		if (l <= x && y <= r && t[k].max2 < v)
		{
			int red = (t[k].max1-v)*t[k].max1_cnt;
			//cout << red << "!asdkalsdk\n";
			if (red <= count || !apply)
			{
				if (apply) 
				{
					t[k].tag = min(t[k].tag, v);
					propagate(k);
				}
				return min(red, count);	
			}
		}
		if (k < n)
		{
			int m = (x+y)/2;
			int val1 = set_min(l, r, v, apply, count, k*2, x, m);
			count -= val1;
			int val2 = set_min(l, r, v, apply, count, k*2+1, m, y);
			count -= val2;
			merge(t[k], t[k*2], t[k*2+1]);
			return val1 + val2;
		}
		return 0;
	}

	int get(int l, int r, int k=1, int x=0, int y=-1)
	{
		if (y == -1) y = n;
		propagate(k);
		if (l <= x && y <= r) return t[k].sum;
		if (r <= x || y <= l) return 0;
		int m = (x+y)/2;
		return get(l, r, k*2, x, m) + get(l, r, k*2+1, m, y);
	}
};
segtree *seg;

void print()
{
	for (int i = 0; i < seg->n; i++)
	{
		//cout << seg->get(i, i+1) << ", ";
	}
	cout << "\n";
}

void initialise(int N, int Q, int h_[]) 
{
	vector < int > h(N);
	for (int i = 0; i < N; i++) h[i] = h_[i+1];
	seg = new segtree(h);
}

void cut(int l, int r, int k) 
{
	l--;
	int x = 0, y = seg->t[1].max1;
	while(x < y-1)
	{
		int m = (x+y)/2;
		if (seg->set_min(l, r, m, false, k) < k)
		{
			y = m;
		}
		else
		{
			x = m;
		}
	}
	//cout << "riduco fino a :" << y << "!\n";
	//print();
	k -= seg->set_min(l, r, y, true, k);
	//print();

	//cout << "poto altri :" << k << "!\n";
	seg->set_min(l, r, x, true, k);
	//print();
}

void magic(int i, int x) 
{
	seg->set(i-1, x);
}

long long int inspect(int l, int r) 
{
	return seg->get(l-1, r);
}

Compilation message (stderr)

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29