#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#include "towers.h"
#include <vector>
int st=0;
int n;
vector<int> it;
int tree[4*200001][2];
void build(int no,int l,int r){
if(l==r){
tree[no][0]=it[l];
tree[no][1]=it[l];
}
else{
int mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
tree[no][0]=min(tree[no*2+1][0],tree[no*2+2][0]);
tree[no][1]=max(tree[no*2+1][1],tree[no*2+2][1]);
}
}
int query(int no,int l,int r,int aa,int bb){
if(r<aa or l>bb or aa>bb){
return 1e9+1;
}
if(aa<=l and r<=bb){
return tree[no][0];
}
int mid=(l+r)/2;
return min(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
int query2(int no,int l,int r,int aa,int bb){
if(r<aa or l>bb or aa>bb){
return -1;
}
if(aa<=l and r<=bb){
return tree[no][1];
}
int mid=(l+r)/2;
return max(query2(no*2+1,l,mid,aa,bb),query2(no*2+2,mid+1,r,aa,bb));
}
vector<pair<int,int>> mm;
void init(int nn, vector<int> ita) {
n=nn;
it=ita;
st=0;
build(0,0,n-1);
}
int le[100001];
int re2[100001];
void rec(int l,int r){
mm.clear();
vector<pair<llo,llo>> ss;
for(int i=r;i>=l;i--){
while(ss.size()){
if(ss.back().a<it[i]){
ss.pop_back();
}
else{
break;
}
}
re2[i]=n-1;
if(ss.size()){
re2[i]=ss.back().b-1;
}
ss.pb({it[i],i});
}
ss.clear();
for(int i=l;i<=r;i++){
while(ss.size()){
if(ss.back().a<it[i]){
ss.pop_back();
}
else{
break;
}
}
le[i]=0;
if(ss.size()){
le[i]=ss.back().b+1;
}
ss.pb({it[i],i});
}
for(int i=0;i<n;i++){
int x=it[i]-query(0,0,n-1,le[i],i);
int y=it[i]-query(0,0,n-1,i,re2[i]);
mm.pb({0,min(x,y)});
}
}
int re[100001][2];
int par[200001][20];
set<pair<int,int>> xx[2];
vector<pair<pair<int,int>,int>> yy;
map<int,int> kk;
int max_towers(int l, int r, int d) {
int ans=0;
rec(l,r);
for(auto j:mm){
if(d>=j.a and d<=j.b){
ans++;
}
}
return ans+1;
if(kk.find(d)==kk.end()){
llo ind=n;
kk[d]++;
yy.clear();
xx[0].clear();
xx[1].clear();
for(int i=n-1;i>=0;i--){
llo cur=query(0,0,n-1,i+1,ind-1);
if(cur<=it[i]-d){
llo zz=ind-1;
while(zz>i){
zz--;
if(query(0,0,n-1,i+1,zz)<=it[i]-d){
continue;
}
else{
zz++;
break;
}
}
xx[0].insert({i,yy.size()});
yy.pb({{i,zz},0});
re[i][0]=zz;
ind=zz;
}
else{
re[i][0]=-1;
}
}
ind=n;
for(int i=n-1;i>=0;i--){
llo cur=query2(0,0,n-1,i+1,ind-1);
if(cur>=it[i]+d){
llo zz=ind-1;
while(zz>i){
zz--;
if(query2(0,0,n-1,i+1,zz)>=it[i]+d){
continue;
}
else{
zz++;
break;
}
}
re[i][1]=zz;
xx[1].insert({i,yy.size()});
yy.pb({{i,zz},1});
ind=zz;
}
else{
re[i][1]=-1;
}
}
for(int i=0;i<yy.size();i++){
par[i][0]=-1;
auto j=xx[1-yy[i].b].lower_bound({yy[i].a.b,-1});
if(j!=xx[1-yy[i].b].end()){
par[i][0]=(*j).b;
// cout<<i<<":"<<(*j).b<<endl;
}
}
for(int j=1;j<20;j++){
for(int i=0;i<yy.size();i++){
if(par[i][j-1]==-1){
par[i][j]=-1;
}
else{
par[i][j]=par[par[i][j-1]][j-1];
}
}
}
/* for(auto j:yy){
cout<<j.a.a<<","<<j.a.b<<","<<j.b<<endl;
}
*/
st=1;
}
// cout<<l<<",,,,"<<-1<<endl;
/* for(auto j:xx[1]){
cout<<j.a<<"//"<<j.b<<endl;
}*/
auto j=xx[1].lower_bound({l,-1});
if(j==xx[1].end()){
return 1;
}
int cot=(*j).b;
//cout<<cot<<":::::"<<yy[cot].a.b<<endl;
// cout<<((*j).a)<<"<<"<<endl;
if(yy[cot].a.b>r){
return 1;
}
//cout<<22<<endl;
int su=1;
//cout<<cot<<";;"<<endl;
//cout<<par[cot][0]<<":"<<par[cot][1]<<":"<<par[cot][2]<<endl;
//cout<<par[cot][0]<<";;"<<yy[par[cot][0]].a.b<<";;"<<endl;
for(int j=19;j>=0;j--){
if(par[cot][j]>=0){
// cout<<yy[par[cot][j]].a.b<<";"<<j<<endl;
if(yy[par[cot][j]].a.b<=r){
cot=par[cot][j];
su+=(1<<j);
}
}
}
//cout<<su<<",,,,"<<endl;
return ((su)/2)+1;
}
Compilation message
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:169:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for(int i=0;i<yy.size();i++){
| ~^~~~~~~~~~
towers.cpp:178:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | for(int i=0;i<yy.size();i++){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4057 ms |
4484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4013 ms |
5200 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4030 ms |
1616 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4057 ms |
4484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
