oj.uz

Submission #590210

# Submission time Handle Problem Language Result Execution time Memory
590210 2022-07-05T16:35:25 Z franfill Weirdtree (RMI21_weirdtree) C++17
21 / 100
 2000 ms 49732 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 && !apply) 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 2 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 2 ms 340 KB Output is correct
3 Correct 197 ms 12088 KB Output is correct
4 Correct 316 ms 13236 KB Output is correct

Subtask #3
8.0 / 8.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 340 KB Output is correct
2 Correct 10 ms 448 KB Output is correct
3 Execution timed out 2084 ms 48320 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 44604 KB Output is correct
2 Execution timed out 2035 ms 49732 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 197 ms 12088 KB Output is correct
4 Correct 316 ms 13236 KB Output is correct
5 Correct 9 ms 340 KB Output is correct
6 Correct 10 ms 448 KB Output is correct
7 Correct 192 ms 13304 KB Output is correct
8 Correct 322 ms 13264 KB Output is correct
9 Correct 193 ms 13196 KB Output is correct
10 Correct 319 ms 13440 KB Output is correct
11 Correct 200 ms 13340 KB Output is correct
12 Correct 87 ms 12996 KB Output is correct
13 Execution timed out 2085 ms 12628 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 197 ms 12088 KB Output is correct
4 Correct 316 ms 13236 KB Output is correct
5 Correct 9 ms 340 KB Output is correct
6 Correct 10 ms 448 KB Output is correct
7 Execution timed out 2084 ms 48320 KB Time limit exceeded
8 Halted 0 ms 0 KB -