#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL<<(i))
namespace trung{
const ll MAXN = 2e5+100;
const ll INF = 1e9+7;
ll n,k;
vector <ll> val;
namespace seg{
pll tree[MAXN*4+100];
ll lazy[MAXN*4+100];
pll combine(pll x,pll y){
if (x.fi > y.fi)return y;
else return x;
}
void build(ll id=1,ll l=0,ll r=n-1){
if (l==r){tree[id] = MP(val[l],l);}
else{
ll mid = (l + r) >> 1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
tree[id] = combine(tree[id<<1],tree[id<<1|1]);
}
}
void push(ll id,ll x){
tree[id].fi+=x;
lazy[id]+=x;
}
void lz(ll id){
push(id<<1,lazy[id]);
push(id<<1|1,lazy[id]);
lazy[id] = 0;
}
void update(ll l1,ll r1,ll id=1,ll l=0,ll r=n-1){
// if (id==1)cout<<"UPD "<<l1<<' '<<r1<<endl;
if (l1 > r || l > r1 || l1 > r1)return;
if (l1 <= l && r <= r1){
push(id,-1);
return;
}
lz(id);
ll mid = (l + r) >> 1;
update(l1,r1,id<<1,l,mid);
update(l1,r1,id<<1|1,mid+1,r);
tree[id] = combine(tree[id<<1],tree[id<<1|1]);
}
void del(ll i,ll id=1,ll l=0,ll r=n-1){
if (l > i || i > r)return;
if (l==r){
tree[id].fi = INF;
return;
}
lz(id);
ll mid = (l + r) >> 1;
del(i,id<<1,l,mid);
del(i,id<<1|1,mid+1,r);
tree[id] = combine(tree[id<<1],tree[id<<1|1]);
}
ll get(ll l1,ll r1,ll id=1,ll l=0,ll r=n-1){
if (l1 > r || l > r1 || l1 > r1)return n+1;
if (tree[id].fi!=0)return n+1;
if (l1 <= l && r <= r1)return tree[id].se;
lz(id);
ll mid = (l + r) >> 1;
ll res = get(l1,r1,id<<1,l,mid);
if (res==n+1)res = get(l1,r1,id<<1|1,mid+1,r);
return res;
}
}
ll h[MAXN];
ll label;
vector <ll> all;
void solve(ll x){
ll l = x-k+1,r=x-1;
// cout<<x<<' '<<l<<' '<<r<<endl;
ll tmp;
while ((tmp=seg::get(l+n,r+n)) != n+1){
solve(tmp);
}
while ((tmp=seg::get(l,r)) != n+1){
solve(tmp);
}
all.push_back(x);
}
}
void init(int K, std::vector<int> r){
using namespace trung;
val = r;
n=sz(r);
k=K;
seg::build();
// cout<<"OK"<<endl;
ll cur;
label = n;
while ((cur=seg::get(0,n-1)) != n+1){
// cout<<"CUR "<<cur<<endl;
solve(cur);
for (auto x:all){
h[x] = --label;
ll l = x-k+1,r=x-1;
seg::update(l,r);
seg::update(l+n,r+n);
seg::del(x);
}
all.clear();
}
}
int compare_plants(int x, int y){
using namespace trung;
return (h[x] > h[y] ? 1 : -1);
}
Compilation message
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:96:11: error: no match for 'operator=' (operand types are 'std::vector<long long int>' and 'std::vector<int>')
96 | val = r;
| ^
In file included from /usr/include/c++/10/vector:72,
from plants.h:1,
from plants.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
198 | vector<_Tp, _Alloc>::
| ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note: no known conversion for argument 1 from 'std::vector<int>' to 'const std::vector<long long int>&'
199 | operator=(const vector<_Tp, _Alloc>& __x)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
from plants.h:1,
from plants.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
709 | operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note: no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<long long int>&&'
709 | operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
| ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
730 | operator=(initializer_list<value_type> __l)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note: no known conversion for argument 1 from 'std::vector<int>' to 'std::initializer_list<long long int>'
730 | operator=(initializer_list<value_type> __l)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
