#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<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];
int cc[100001][20];
int dd[100001][20];
int val[100001];
int tree2[4*200001];
int tree3[4*200001];
void build2(int no,int l,int r){
if(l==r){
tree2[no]=le[l];
tree3[no]=re2[l];
}
else{
int mid=(l+r)/2;
build2(no*2+1,l,mid);
build2(no*2+2,mid+1,r);
tree2[no]=min(tree2[no*2+1],tree2[no*2+2]);
tree3[no]=max(tree3[no*2+1],tree3[no*2+2]);
}
}
int find(int no,int l,int r,int aa,int bb,int x){
//find first with val less than x
if(r<aa or l>bb or aa>bb){
return -1;
}
if(l==r){
if(tree2[no]<x){
return l;
}
return -1;
}
if(tree2[no]>=x){
return -1;
}
int mid=(l+r)/2;
int xx=find(no*2+1,l,mid,aa,bb,x);
if(xx>=0){
return xx;
}
return find(no*2+2,mid+1,r,aa,bb,x);
}
int find2(int no,int l,int r,int aa,int bb,int x){
//find first with val less than x
if(r<aa or l>bb or aa>bb){
return -1;
}
if(l==r){
if(tree2[no]>x){
return l;
}
return -1;
}
if(tree2[no]<=x){
return -1;
}
int mid=(l+r)/2;
int xx=find2(no*2+2,mid+1,r,aa,bb,x);
if(xx>=0){
return xx;
}
return find2(no*2+1,l,mid,aa,bb,x);
}
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;
if(ss.size()){
re2[i]=ss.back().b;
}
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]=-1;
if(ss.size()){
le[i]=ss.back().b;
}
ss.pb({it[i],i});
}
for(int i=0;i<n;i++){
int x=it[i]-query(0,0,n-1,le[i]+1,i);
int y=it[i]-query(0,0,n-1,i,re2[i]-1);
val[i]=min(x,y);
mm.pb(min(x,y));
}
for(int i=0;i<n;i++){
cc[i][0]=le[i];
dd[i][0]=re2[i];
// cout<<i<<":"<<le[i]<<endl;
// cout<<i<<":"<<re2[i]<<endl;
if(re2[i]==n){
dd[i][0]=-1;
}
}
for(int j=1;j<20;j++){
for(int i=0;i<n;i++){
if(cc[i][j-1]==-1){
cc[i][j]=-1;
}
else{
cc[i][j]=cc[cc[i][j-1]][j-1];
}
}
}
for(int j=1;j<20;j++){
for(int i=0;i<n;i++){
if(dd[i][j-1]==-1){
dd[i][j]=-1;
}
else{
dd[i][j]=dd[dd[i][j-1]][j-1];
}
}
}
build2(0,0,n-1);
sort(mm.begin(),mm.end());
}
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) {
if(st==0){
rec(0,n-1);
st=1;
}
//cout<<dd[0][0]<<"???"<<endl;
llo low=mm.size();
llo su=0;
for(int i=l;i<=r;i++){
if(val[i]>=d){
su++;
}
}
int ind=find(0,0,n-1,l,r,l);
/* for(int i=l;i<=r;i++){
if(cc[i][0]<l){
ind=i;
break;
}
}*/
int ind2=ind;
for(int j=19;j>=0;j--){
if(dd[ind2][j]<=r and dd[ind2][j]>=0){
ind2=dd[ind2][j];
}
}
vector<llo> ss;
int ind3=-1;
if(query(0,0,n-1,l,ind-1)>it[ind]-d){
for(int j=19;j>=0;j--){
if(dd[ind][j]<=r and dd[ind][j]>=0){
if(query(0,0,n-1,l,dd[ind][j]-1)>it[dd[ind][j]]-d){
ind=dd[ind][j];
}
}
}
ind3=ind;
while(true){
ss.pb(ind3);
if(ind3==ind){
break;
}
ind3=dd[ind3][0];
}
}
pair<int,int> ll={ind3,ind};
//from ind3 to ind
//return su;
vector<int> tt;
ind=-1;
ind=find2(0,0,n-1,l,r,r);
/* for(int i=r;i>=l;i--){
if(dd[i][0]>r or dd[i][0]==-1){
ind=i;
break;
}
}*/
ind3=-1;
if(query(0,0,n-1,ind+1,r)<=it[ind]-d){
}
else{
ind3=ind;
for(int j=19;j>=0;j--){
if(cc[ind][j]>=l){
if(query(0,0,n-1,cc[ind][j]+1,r)>it[cc[ind][j]]-d){
ind=cc[ind][j];
}
}
}
while(true){
tt.pb(ind3);
if(ind3==ind){
break;
}
ind3=cc[ind3][0];
}
}
pair<int,int> rr={ind3,ind};
for(auto j:ss){
if(val[j]>=d){
su--;
}
}
for(auto j:tt){
if(val[j]>=d){
su--;
}
}
if(ll.a>=0 and rr.a>=0){
if(rr.b==ind2 and ll.b==ind2){
if(val[rr.b]>=d){
su--;
}
}
}
su++;
return su;
}
Compilation message
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:205:6: warning: unused variable 'low' [-Wunused-variable]
205 | llo low=mm.size();
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1191 ms |
14120 KB |
5th 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: '14' |
| 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: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2376 ms |
22764 KB |
8th lines differ - on the 1st token, expected: '9', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
762 ms |
5812 KB |
Output is correct |
| 2 |
Execution timed out |
4034 ms |
22860 KB |
Time limit exceeded |
| 3 |
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: '14' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1191 ms |
14120 KB |
5th lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
