#include "weirdtree.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
const int maxn = 3e5 + 200, maxm = 1e4 + 200, inf = 1e9;
int n;
struct node{
ll sum = 0;
ll max1 = 0;
ll max2 = 0;
ll fr = 0;
} t[maxn * 4];
ll mv[maxn * 4];
node merge(node a, node b){
node c;
c.sum = a.sum + b.sum;
c.max1 = max(a.max1, b.max1);
if (a.max1 == b.max1){
c.fr = a.fr + b.fr;
c.max2 = max(a.max2, b.max2);
}
else{
if (a.max1 > b.max1){
c.fr = a.fr;
c.max2 = max(a.max2, b.max1);
}
else{
c.fr = b.fr;
c.max2 = max(b.max2, a.max1);
}
}
return c;
}
void push(int v, int l, int r){
if (mv[v]){
t[v].sum += mv[v] * t[v].fr;
t[v].max1 += mv[v];
/* if (t[v].sum < 0){
cout << v << " " << l << " " << r << '\n';
cout << mv[v] << " " << t[v].fr << '\n';
cout << t[v].max1 << '\n';
cout << t[v].sum << '\n';
exit(0);
}*/
if (l != r){
mv[v + v] += mv[v];
mv[v + v + 1] += mv[v];
}
mv[v] = 0;
}
}
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if (tl == tr){
t[v].sum = val;
t[v].max1 = val;
t[v].fr = 1;
t[v].max2 = 0;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm){
upd(pos, val, v + v, tl, tm);
}
else{
upd(pos, val, v + v + 1, tm + 1, tr);
}
push(v + v, tl, tm);
push(v + v + 1, tm + 1, tr);
t[v] = merge(t[v + v], t[v + v + 1]);
/* if (val == 1000){
cout << v << " " << tl << " " << tr << '\n';
cout << t[v].sum << '\n';
cout << t[v + v].sum << " " << t[v + v + 1].sum << '\n';
}*/
}
node get(int l, int r, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if (l <= tl && tr <= r){
return t[v];
}
if (l > tr || r < tl){
node cl;
cl.sum = 0;
cl.max1 = 0;
cl.max2 = 0;
cl.fr = 0;
return cl;
}
int tm = (tl + tr) / 2;
return merge(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}
void updlr(int l, int r, int x, int mx, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if (l > tr || r < tl || t[v].max1 < mx)
return;
if (l <= tl && tr <= r && t[v].max1 - x > t[v].max2 && t[v].max1 == mx){
mv[v] -= x;
push(v, tl, tr);
return;
}
if (tl == tr && t[v].max1 == mx){
mv[v] -= (x);
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
updlr(l, r, x, mx, v + v, tl, tm);
updlr(l, r, x, mx, v + v + 1, tm + 1, tr);
t[v] = merge(t[v + v], t[v + v + 1]);
}
void updlr2(int l, int r, int x, int &y, int mx, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if (l > tr || r < tl || t[v].max1 < mx){
return;
}
if (l <= tl && tr <= r && t[v].max1 - x - (y > 0) > t[v].max2 && (y == 0 || y >= t[v].fr) && t[v].max1 == mx){
mv[v] -= (x + (y > 0));
y = max(0ll, y - t[v].fr);
push(v, tl, tr);
return;
}
if (tl == tr && t[v].max1 == mx && (y == 0 || y >= t[v].fr)){
mv[v] -= (x + (y > 0));
y = max(0ll, y - t[v].fr);
push(v, tl, tr);
return;
}
if (tl == tr){
return;
}
int tm = (tl + tr) / 2;
updlr2(l, r, x, y, mx, v + v, tl, tm);
updlr2(l, r, x, y, mx, v + v + 1, tm + 1, tr);
t[v] = merge(t[v + v], t[v + v + 1]);
}
ll gets(int l, int r, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if (l <= tl && tr <= r)
return t[v].sum;
if (l > tr || r < tl)
return 0;
int tm = (tl + tr) / 2;
return gets(l, r, v + v, tl, tm) + gets(l, r, v + v + 1, tm + 1, tr);
}
void initialise(int N, int Q, int h[]) {
n = N;
for (int i = 1; i <= n; ++i){
upd(i, h[i]);
}
}
void cut(int l, int r, int k) {
while (k > 0){
node cur = get(l, r);
if (cur.max1 == 0){
break;
}
ll rz = cur.max1 - cur.max2;
if (rz * cur.fr <= k){
int is = 0;
updlr(l, r, rz, cur.max1);
k -= rz * cur.fr;
}
else{
ll all = rz * cur.fr;
int is = k % cur.fr;
updlr2(l, r, k / cur.fr, is, cur.max1);
k = 0;
break;
}
}
}
void magic(int i, int x) {
upd(i, x);
}
long long int inspect(int l, int r) {
// Your code here.
return gets(l, r);
}
Compilation message
weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:197:17: warning: unused variable 'is' [-Wunused-variable]
197 | int is = 0;
| ^~
weirdtree.cpp:202:16: warning: unused variable 'all' [-Wunused-variable]
202 | ll all = rz * cur.fr;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
227 ms |
44132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
