oj.uz

Submission #590211

# Submission time Handle Problem Language Result Execution time Memory
590211 2022-07-05T16:36:14 Z franfill Weirdtree (RMI21_weirdtree) C++17
100 / 100
 1691 ms 52524 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 204 ms 11476 KB Output is correct
4 Correct 269 ms 11476 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 340 KB Output is correct
2 Correct 8 ms 444 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 340 KB Output is correct
2 Correct 8 ms 444 KB Output is correct
3 Correct 1673 ms 45628 KB Output is correct
4 Correct 1242 ms 52524 KB Output is correct
5 Correct 1691 ms 52360 KB Output is correct
6 Correct 1214 ms 52324 KB Output is correct
7 Correct 92 ms 11476 KB Output is correct
8 Correct 178 ms 11592 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 11476 KB Output is correct
2 Correct 178 ms 11592 KB Output is correct
3 Correct 583 ms 44636 KB Output is correct
4 Correct 934 ms 45240 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 204 ms 11476 KB Output is correct
4 Correct 269 ms 11476 KB Output is correct
5 Correct 8 ms 340 KB Output is correct
6 Correct 8 ms 444 KB Output is correct
7 Correct 92 ms 11476 KB Output is correct
8 Correct 178 ms 11592 KB Output is correct
9 Correct 194 ms 11476 KB Output is correct
10 Correct 272 ms 11476 KB Output is correct
11 Correct 192 ms 11476 KB Output is correct
12 Correct 279 ms 11520 KB Output is correct
13 Correct 201 ms 11472 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 204 ms 11476 KB Output is correct
4 Correct 269 ms 11476 KB Output is correct
5 Correct 8 ms 340 KB Output is correct
6 Correct 8 ms 444 KB Output is correct
7 Correct 1673 ms 45628 KB Output is correct
8 Correct 1242 ms 52524 KB Output is correct
9 Correct 1691 ms 52360 KB Output is correct
10 Correct 1214 ms 52324 KB Output is correct
11 Correct 583 ms 44636 KB Output is correct
12 Correct 934 ms 45240 KB Output is correct
13 Correct 194 ms 11476 KB Output is correct
14 Correct 272 ms 11476 KB Output is correct
15 Correct 192 ms 11476 KB Output is correct
16 Correct 279 ms 11520 KB Output is correct
17 Correct 201 ms 11472 KB Output is correct
18 Correct 92 ms 11476 KB Output is correct
19 Correct 178 ms 11592 KB Output is correct
20 Correct 875 ms 51592 KB Output is correct
21 Correct 1202 ms 52024 KB Output is correct
22 Correct 900 ms 52012 KB Output is correct
23 Correct 1237 ms 52056 KB Output is correct
24 Correct 885 ms 51876 KB Output is correct