#include<bits/stdc++.h>
#include "towers.h"
using namespace std;
const int N=2000000009;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[100009],K,pas,L,R,D,seg[400009],l,r,z,za,PI,bo[100009],VAL[100009];
vector <pair <int, int> > ANS;
multiset <int> s;
multiset <int>::iterator it,tt;
multiset <pair <int, int> > S;
multiset <pair <int, int> >::iterator IT,TT;
pair <int, int> P[100009];
void read(int q, int w, int rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
z=max(z,seg[rr]);
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
void UPD(int i){
int D;
multiset <int>::iterator it,tt;
multiset <pair <int, int> >::iterator IT,TT;
tt=s.lower_bound(i);
tt++;
if(tt==s.end()){
R=a+1;
}else{
R=(*tt);
}
it=s.lower_bound(i);
if(it==s.begin()){
L=0;
}else{
it--;
L=(*it);
}
L++;R--;
z=0;
l=i+1;r=R;
if(l<=r) read(1,za,1);
if(r==a) z=N;
e=z;
z=0;
l=L;r=i-1;
if(l<=r) read(1,za,1);
if(l==1) z=N;
e=min(e,z);
S.erase({VAL[i],i});
S.insert({e-f[i]+1,i});
}
void init(int NN, std::vector<int> HH) {
a=NN;
for(i=1; i<=a; i++){
f[i]=HH[i-1];
}
za=1;
while(za<a) za*=2;
for(i=1; i<=a; i++){
seg[za+i-1]=f[i];
}
for(i=za-1; i>=1; i--){
seg[i]=max(seg[i*2],seg[i*2+1]);
}
for(i=1; i<=a; i++){
PI++;P[PI]={f[i],i};
}
sort(P+1,P+PI+1);
D=1;
for(ii=1; ii<=PI; ii++){
i=P[ii].second;
tt=s.lower_bound(i);
if(tt==s.end()){
R=a+1;
}else{
R=(*tt);
}
it=s.lower_bound(i);
if(it==s.begin()){
L=0;
}else{
it--;
L=(*it);
}
L++;R--;
e=0;
z=0;
l=i+1;r=R;
if(l<=r) read(1,za,1);
if(r==a) z=N;
if(z<f[i]+D){
e++;
}
z=0;
l=L;r=i-1;
if(l<=r) read(1,za,1);
if(l==1) z=N;
if(z<f[i]+D){
e++;
}
if(e>0) continue;
s.insert(i);bo[i]=1;
}
ANS.push_back({1,s.size()});
//cout<<s.size()<<"\n";
for(i=1; i<=a; i++){
if(bo[i]==0) continue;
tt=s.lower_bound(i);
tt++;
if(tt==s.end()){
R=a+1;
}else{
R=(*tt);
}
it=s.lower_bound(i);
if(it==s.begin()){
L=0;
}else{
it--;
L=(*it);
}
L++;R--;
z=0;
l=i+1;r=R;
if(l<=r) read(1,za,1);
if(r==a) z=N;
e=z;
z=0;
l=L;r=i-1;
if(l<=r) read(1,za,1);
if(l==1) z=N;
e=min(e,z);
S.insert({e-f[i]+1,i});
VAL[i]=e-f[i]+1;
}
/*for(i=1; i<=a; i++){
if(bo[i]==0) continue;
cout<<i<<" "<<VAL[i]<<"\n";
}*/
while(s.size()>1){
IT=S.begin();
D=(*IT).first;
i=(*IT).second;
S.erase(IT);
s.erase(i);
tt=s.lower_bound(i);
if(tt!=s.end()){
UPD((*tt));
}
it=tt;
if(it!=s.begin()){
it--;
UPD((*it));
}
IT=S.begin();
//if((*IT).first>D){
ANS.push_back({D,s.size()});
//}
}
}
int max_towers(int LL, int RR, int DD) {
pas=1;LL++;RR++;
L=LL;R=RR;D=DD;
c=lower_bound(ANS.begin(),ANS.end(),make_pair(D+1,0))-ANS.begin();
c--;
pas=ANS[c].second;
return pas;
}
Compilation message
towers.cpp: In function 'void UPD(int)':
towers.cpp:22:9: warning: unused variable 'D' [-Wunused-variable]
22 | int D;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
339 ms |
1872 KB |
1st lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1185 ms |
32356 KB |
1st lines differ - on the 1st token, expected: '11903', found: '33010' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
277 ms |
4760 KB |
1st lines differ - on the 1st token, expected: '7197', found: '7196' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
339 ms |
1872 KB |
1st lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
