Submission #590211

#	Time	Username	Problem	Language	Result	Execution time	Memory
590211		franfill	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	1691 ms	52524 KiB

weirdtree

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

struct segtree
{
	struct node
	{
		ll max1=-(1<<30), max2=-(1<<30);
		ll max1_cnt = 0;
		ll sum=0;
		ll tag = 1<<30;
		node(){};
		node(ll v)
		{
			sum = v;
			max1_cnt = 1;
			max1 = v;
			max2 = -(1<<30);
		}
		
	};

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

	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(ll k)
	{
		if (t[k].tag < t[k].max1)
		{
			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(ll i, ll val, ll k=1, ll x=0, ll 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;
		ll 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]);
	}

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

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

		if (l <= x && y <= r && t[k].max2 < v)
		{
			ll red = (t[k].max1-v)*t[k].max1_cnt;
			if (red <= count || !apply)
			{
				if (apply) 
				{
					t[k].tag = min(t[k].tag, v);
					propagate(k);
				}
				return min(red, count);	
			}
		}
		if (k < n)
		{
			ll m = (x+y)/2;
			ll val1 = set_min(l, r, v, apply, count, k*2, x, m);
			count -= val1;
			ll 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;
	}

	ll get(ll l, ll r, ll k=1, ll x=0, ll 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;
		ll 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 (ll i = 0; i < seg->n; i++)
	{
		//cout << seg->get(i, i+1) << ", ";
	}
	cout << "\n";
}

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

void cut(int l, int r, int k) 
{
	l--;
	ll x = 0, y = seg->t[1].max1+1;
	while(x < y-1)
	{
		ll 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<long long int>&)':
weirdtree.cpp:29:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (n = 1; n < v.size(); n *= 2);
      |               ~~^~~~~~~~~~
weirdtree.cpp:31:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (ll i = 0; i < v.size(); i++) t[i+n] = node(v[i]);
      |                  ~~^~~~~~~~~~

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