#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define maxn 200200
#define inf 1000000
#define pii pair<int,int>
#define debug
#define pb push_back
int N,K;
int T[4*maxn];
int id[4*maxn];
int lazy[8*maxn];
int H[2][maxn];
void refresh(int ini,int fim,int p){
lazy[2*p] += lazy[p];
lazy[2*p+1] += lazy[p];
T[p] -= lazy[p];
lazy[p] = 0;
}
void upd(int ini,int fim,int p,int pos,int val){
refresh(ini,fim,p);
if(pos < ini || pos > fim) return;
if(ini == fim){
T[p] = val;
id[p] = pos;
return;
}
int mid = (ini+fim)/2;
upd(ini,mid,2*p,pos,val);
upd(mid+1,fim,2*p+1,pos,val);
if(T[2*p] < T[2*p+1]){
T[p] = T[2*p];
id[p] = id[2*p];
}
else {
T[p] = T[2*p+1];
id[p] = id[2*p+1];
}
}
void dec(int ini,int fim,int p,int l,int r){
refresh(ini,fim,p);
if(l > fim || r < ini)
return;
if(ini >= l && fim <= r){
lazy[p]++;
refresh(ini,fim,p);
return;
}
int mid = (ini+fim)/2;
dec(ini,mid,2*p,l,r);
dec(mid+1,fim,2*p+1,l,r);
if(T[2*p] < T[2*p+1]){
T[p] = T[2*p];
id[p] = id[2*p];
}
else {
T[p] = T[2*p+1];
id[p] = id[2*p+1];
}
}
vector<int> zeroes(){
vector<int> ret;
while(T[1] == 0){
int pos = id[1];
ret.pb(pos);
upd(0,N-1,1,pos,inf);
}
return ret;
}
set<pii> S;
set<pii> Si;
set<int> Sgg;
pii rev(pii a){
return {a.second,a.first};
}
void add(int x){
debug("add %d:\n",x);
if(S.size() == 0){
S.insert({x,N});
Si.insert({N,x});
if(N >= K) Sgg.insert(x);
return;
}
pii nx;
if(S.lower_bound({x,inf}) != S.end())
nx = *S.lower_bound({x,inf});
else {
nx = *S.begin();
}
pii lst;
if(S.lower_bound({x,inf}) != S.begin())
lst = *--S.lower_bound({x,inf});
else {
lst = *--S.end();
lst.first -= N;
}
debug(" -(%d,%d)\n",nx.first,nx.second);
S.erase(S.find(nx));
Si.erase(Si.find(rev(nx)));
if(Sgg.find(nx.first) != Sgg.end())
Sgg.erase(Sgg.find(nx.first));
if(nx.first < x)
nx.first += N;
debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
S.insert({nx.first%N,nx.first-x});
if(nx.first-x >= K)
Sgg.insert(nx.first%N);
Si.insert({nx.first-x,nx.first%N});
debug(" +(%d,%d)\n",x,x-lst.first);
S.insert({x,x-lst.first});
if(x-lst.first >= K)
Sgg.insert(x);
Si.insert({x-lst.first,x});
debug("\n\n");
}
void rem(int x){
debug("rem %d:\n",x);
if(S.size() == 1){
S.clear();
Si.clear();
Sgg.clear();
return;
}
pii it = *S.lower_bound({x,-1});
pii nx;
if(S.lower_bound({x,inf}) != S.end())
nx = *S.lower_bound({x,inf});
else
nx = *S.begin();
debug(" -(%d,%d)\n",it.first,it.second);
debug(" -(%d,%d)\n",nx.first,nx.second);
S.erase(S.find(it));
Si.erase(Si.find(rev(it)));
if(Sgg.find(it.first) != Sgg.end())
Sgg.erase(Sgg.find(it.first));
S.erase(S.find(nx));
Si.erase(Si.find(rev(nx)));
if(Sgg.find((nx.first)) != Sgg.end())
Sgg.erase(Sgg.find(nx.first));
debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
S.insert({nx.first,nx.second+it.second});
Si.insert({nx.second+it.second,nx.first});
if(nx.second+it.second >= K)
Sgg.insert(nx.first);
}
int X,FX;
int consX;
int acha(){
debug("tem %d\n",(int)S.size());
//return *Sgg.begin();
if(FX){
if(*SS.begin() == 0)
return 0;
if(consX)
return *Sgg.begin();
else
return *--Sgg.end();
}
if(Si.size() == 1 || FX)
return (--Si.end()) -> second;
int ret = (--Si.end()) -> second;
if(FX == 0 && ret == X && S.size() > 1){
pii retret = *----Si.end();
if(retret.first >= K)
return retret.second;
}
return ret;
}
void go(int n, int k, int x, vector<int> r,int fastx){
S.clear();
Si.clear();
N = n;
X = x;
FX = fastx;
K = k;
consX = 1;
for(int i=0;i<n;i++)
upd(0,N-1,1,i,r[i]);
int foi = 0;
while(foi < n){
vector<int> v = zeroes();
for(int i : v){
add(i);
if(i == x) consX = 0;
}
int id = acha();
rem(id);
debug("pega %d\n",id);
H[fastx][id] = n-foi;
foi++;
dec(0,N-1,1,max(0,id-k+1),id-1);
if(id-k+1 < 0)
dec(0,N-1,1,id-k+1+N,N-1);
}
}
void init(int k, std::vector<int> r) {
go(r.size(), k, 0, r, 0);
go(r.size(), k, 0, r, 1);
return;
}
int compare_plants(int x, int y) {
int ans = 0;
if(H[0][x] > H[0][y])
ans++;
else ans--;
if(H[1][x] > H[1][y])
ans++;
else ans--;
return ans/2;
}
Compilation message
plants.cpp: In function 'void add(int)':
plants.cpp:95:8: warning: left operand of comma operator has no effect [-Wunused-value]
95 | debug("add %d:\n",x);
| ^~~~~~~~~~~
plants.cpp:119:8: warning: left operand of comma operator has no effect [-Wunused-value]
119 | debug(" -(%d,%d)\n",nx.first,nx.second);
| ^~~~~~~~~~~~~
plants.cpp:119:25: warning: right operand of comma operator has no effect [-Wunused-value]
119 | debug(" -(%d,%d)\n",nx.first,nx.second);
| ~~~^~~~~
plants.cpp:128:8: warning: left operand of comma operator has no effect [-Wunused-value]
128 | debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
| ^~~~~~~~~~~~~
plants.cpp:128:30: warning: right operand of comma operator has no effect [-Wunused-value]
128 | debug(" +(%d,%d)\n",nx.first%N,nx.first-x);
| ~~~~~~~~^~
plants.cpp:133:8: warning: left operand of comma operator has no effect [-Wunused-value]
133 | debug(" +(%d,%d)\n",x,x-lst.first);
| ^~~~~~~~~~~~~
plants.cpp:133:30: warning: right operand of comma operator has no effect [-Wunused-value]
133 | debug(" +(%d,%d)\n",x,x-lst.first);
| ^~~~~
plants.cpp:138:8: warning: statement has no effect [-Wunused-value]
138 | debug("\n\n");
| ~^~~~~~~
plants.cpp: In function 'void rem(int)':
plants.cpp:143:8: warning: left operand of comma operator has no effect [-Wunused-value]
143 | debug("rem %d:\n",x);
| ^~~~~~~~~~~
plants.cpp:161:8: warning: left operand of comma operator has no effect [-Wunused-value]
161 | debug(" -(%d,%d)\n",it.first,it.second);
| ^~~~~~~~~~~~~
plants.cpp:161:25: warning: right operand of comma operator has no effect [-Wunused-value]
161 | debug(" -(%d,%d)\n",it.first,it.second);
| ~~~^~~~~
plants.cpp:162:8: warning: left operand of comma operator has no effect [-Wunused-value]
162 | debug(" -(%d,%d)\n",nx.first,nx.second);
| ^~~~~~~~~~~~~
plants.cpp:162:25: warning: right operand of comma operator has no effect [-Wunused-value]
162 | debug(" -(%d,%d)\n",nx.first,nx.second);
| ~~~^~~~~
plants.cpp:173:8: warning: left operand of comma operator has no effect [-Wunused-value]
173 | debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
| ^~~~~~~~~~~~~
plants.cpp:173:25: warning: right operand of comma operator has no effect [-Wunused-value]
173 | debug(" +(%d,%d)\n",nx.first,nx.second+it.second);
| ~~~^~~~~
plants.cpp: In function 'int acha()':
plants.cpp:186:8: warning: left operand of comma operator has no effect [-Wunused-value]
186 | debug("tem %d\n",(int)S.size());
| ^~~~~~~~~~
plants.cpp:192:7: error: 'SS' was not declared in this scope; did you mean 'Si'?
192 | if(*SS.begin() == 0)
| ^~
| Si
plants.cpp: In function 'void go(int, int, int, std::vector<int>, int)':
plants.cpp:247:9: warning: left operand of comma operator has no effect [-Wunused-value]
247 | debug("pega %d\n",id);
| ^~~~~~~~~~~
