#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);
}
void print()
{
//cout<<"max1: "<<max1<<" max2: "<<max2<<" sum: "<<sum<<" max1_cnt: "<<max1_cnt<<" tag:"<<tag<<endl;
}
};
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;
//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)
{
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:33: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]
33 | for (n = 1; n < v.size(); n *= 2);
| ~~^~~~~~~~~~
weirdtree.cpp:35: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]
35 | for (ll i = 0; i < v.size(); i++) t[i+n] = node(v[i]);
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
468 KB |
Output is correct |
| 2 |
Correct |
28 ms |
440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
468 KB |
Output is correct |
| 2 |
Correct |
28 ms |
440 KB |
Output is correct |
| 3 |
Execution timed out |
2063 ms |
12500 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
340 KB |
Output is correct |
| 2 |
Correct |
11 ms |
352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
340 KB |
Output is correct |
| 2 |
Correct |
11 ms |
352 KB |
Output is correct |
| 3 |
Execution timed out |
2076 ms |
45932 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2081 ms |
45796 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
468 KB |
Output is correct |
| 2 |
Correct |
28 ms |
440 KB |
Output is correct |
| 3 |
Execution timed out |
2063 ms |
12500 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
468 KB |
Output is correct |
| 2 |
Correct |
28 ms |
440 KB |
Output is correct |
| 3 |
Execution timed out |
2063 ms |
12500 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
