#include "weirdtree.h"
#include<bits/stdc++.h>
#define int long long
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(signed N, signed Q, signed h_[])
{
vector < int > h(N);
for (int i = 0; i < N; i++) h[i] = h_[i+1];
seg = new segtree(h);
}
void cut(signed l, signed r, signed 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(signed i, signed x)
{
seg->set(i-1, x);
}
long long inspect(signed l, signed r)
{
return seg->get(l-1, r);
}
Compilation message
weirdtree.cpp: In constructor 'segtree::segtree(std::vector<long long int>&)':
weirdtree.cpp:34:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (n = 1; n < v.size(); n *= 2);
| ~~^~~~~~~~~~
weirdtree.cpp:36:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int i = 0; i < v.size(); i++) t[i+n] = node(v[i]);
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
436 KB |
Output is correct |
| 2 |
Correct |
10 ms |
464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
436 KB |
Output is correct |
| 2 |
Correct |
10 ms |
464 KB |
Output is correct |
| 3 |
Execution timed out |
2064 ms |
47840 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2070 ms |
44708 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
