#include "weirdtree.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define elif else if
#define ep insert
using namespace std;
struct node{
ll mx1,mx2,sum,f;
};
const int NN=3e5+5;
ll n,a[NN];
node seg[4*NN+5];
map<int,set<int>> mp;
node merge(node x,node y){
int a[4]={x.mx1,x.mx2,y.mx1,y.mx2};
sort(a,a+4);
node z;
z.mx1=a[3];
if (a[2]==a[3]) z.mx2=a[1];
else z.mx2=a[2];
z.sum=x.sum+y.sum;
if (a[2]==a[3]) z.f=x.f+y.f;
elif (x.mx1>y.mx1) z.f=x.f;
else z.f=y.f;
return z;
}
void build(int x,int l,int r){
if (l==r){
seg[x]={a[l],0,a[l],1};
return;
}int mid=(l+r)/2;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
seg[x]=merge(seg[x*2],seg[x*2+1]);
return;
}
void edit(int x,int l,int r,int idx){
if (l==r){
seg[x]={a[l],0,a[l],1};
return;
}int mid=(l+r)/2;
if (idx<=mid) edit(x*2,l,mid,idx);
else edit(x*2+1,mid+1,r,idx);
seg[x]=merge(seg[x*2],seg[x*2+1]);
return;
}
node query(int x,int l,int r,int lx,int rx){
if (l>=lx && r<=rx) return seg[x];
if (l>rx || r<lx) return {INT_MIN,INT_MIN,0,0};
int mid=(l+r)/2;
return merge(query(x*2,l,mid,lx,rx),query(x*2+1,mid+1,r,lx,rx));
}
void initialise(int N, int Q, int h[]) {
n=N;
for (int i=1;i<=n;i++) a[i]=h[i],mp[a[i]].ep(i);
build(1,1,n);
return;
}
void cut(int l, int r, int kk) {
ll k=kk;
while (k>0){
node x=query(1,1,n,l,r);
ll mx1=x.mx1,mx2=x.mx2,f=x.f,d=(mx1-mx2);
if (!mx1) break;
if (k>=d*f){
while (true){
auto it=mp[mx1].lower_bound(l);
if (it==mp[mx1].end() || *it>r) break;
int i=*it;
mp[mx1].erase(it);
mp[mx2].ep(i);
a[i]=mx2;
edit(1,1,n,i);
}
k-=d*f;
continue;
}
int s=k/f+1;
for (int i=0;i<k%f;i++){
int j=*mp[mx1].lower_bound(l);
mp[mx1].erase(j);
mp[mx1-s].ep(j);
a[j]-=s;
edit(1,1,n,j);
}
s=k/f;
while (s){
auto it=mp[mx1].lower_bound(l);
if (it==mp[mx1].end()) break;
if (*it>r) break;
int j=*it;
mp[mx1].erase(it);
mp[mx1-s].ep(j);
a[j]-=s;
edit(1,1,n,j);
}break;
}
//for (int i=1;i<=n;i++) cout<<a[i]<<' ';
//cout<<endl;
return;
}
void magic(int i, int x) {
return;
}
long long int inspect(int l, int r) {
return query(1,1,n,l,r).sum;
}
Compilation message
weirdtree.cpp: In function 'node merge(node, node)':
weirdtree.cpp:16:17: warning: narrowing conversion of 'x.node::mx1' from 'long long int' to 'int' [-Wnarrowing]
16 | int a[4]={x.mx1,x.mx2,y.mx1,y.mx2};
| ~~^~~
weirdtree.cpp:16:23: warning: narrowing conversion of 'x.node::mx2' from 'long long int' to 'int' [-Wnarrowing]
16 | int a[4]={x.mx1,x.mx2,y.mx1,y.mx2};
| ~~^~~
weirdtree.cpp:16:29: warning: narrowing conversion of 'y.node::mx1' from 'long long int' to 'int' [-Wnarrowing]
16 | int a[4]={x.mx1,x.mx2,y.mx1,y.mx2};
| ~~^~~
weirdtree.cpp:16:35: warning: narrowing conversion of 'y.node::mx2' from 'long long int' to 'int' [-Wnarrowing]
16 | int a[4]={x.mx1,x.mx2,y.mx1,y.mx2};
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2648 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2648 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
2744 KB |
Output is correct |
2 |
Correct |
117 ms |
2736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
2744 KB |
Output is correct |
2 |
Correct |
117 ms |
2736 KB |
Output is correct |
3 |
Correct |
679 ms |
81492 KB |
Output is correct |
4 |
Correct |
729 ms |
94736 KB |
Output is correct |
5 |
Correct |
686 ms |
84092 KB |
Output is correct |
6 |
Correct |
646 ms |
92684 KB |
Output is correct |
7 |
Execution timed out |
2052 ms |
14940 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2052 ms |
14940 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2648 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2648 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |