#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(tree3[no]>x){
return l;
}
return -1;
}
if(tree3[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);
}
vector<int> adj[100001];
set<int> xa;
vector<pair<int,int>> yy;
int cot[100001*100];
int ll[100001*100];
int rr[100001*100];
int ba[100001];
int ne=0;
int update(int no,int l,int r,int i,int x){
if(l==r){
int sta=ne;
ne++;
ll[sta]=-1;
rr[sta]=-1;
cot[sta]=cot[no]+x;
return sta;
}
else{
int mid=(l+r)/2;
int sta=ne;
ne++;
if(i<=mid){
rr[sta]=rr[no];
if(ll[no]==-1){
ll[no]=ne;
ne++;
ll[ll[no]]=-1;
rr[ll[no]]=-1;
cot[ll[no]]=0;
}
ll[sta]=update(ll[no],l,mid,i,x);
}
else{
ll[sta]=ll[no];
if(rr[no]==-1){
rr[no]=ne;
ne++;
rr[rr[no]]=-1;
ll[rr[no]]=-1;
cot[rr[no]]=0;
}
rr[sta]=update(rr[no],mid+1,r,i,x);
}
cot[sta]=0;
if(ll[sta]>=0){
cot[sta]+=cot[ll[sta]];
}
if(rr[sta]>=0){
cot[sta]+=cot[rr[sta]];
}
return sta;
}
}
int query5(int no,int l,int r,int aa,int bb){
if(r<aa or l>bb or aa>bb){
return 0;
}
if(aa<=l and r<=bb){
return cot[no];
}
int mid=(l+r)/2;
int su=0;
if(ll[no]>=0){
su+=query5(ll[no],l,mid,aa,bb);
}
if(rr[no]>=0){
su+=query5(rr[no],mid+1,r,aa,bb);
}
return su;
}
void dfs(int no,int par=-1){
if(par==-1){
par=ne;
ll[ne]=-1;
rr[ne]=-1;
ne++;
}
else{
}
if(par!=-1){
ba[no]=update(par,0,n-1,val[no],1);
}
else{
ba[no]=par;
}
for(auto j:adj[no]){
dfs(j,ba[no]);
}
}
vector<int> adj2[100001];
int ba2[100001];
void dfs2(int no,int par=-1){
if(par==-1){
par=ne;
ll[ne]=-1;
rr[ne]=-1;
ne++;
}
else{
}
if(par!=-1){
ba2[no]=update(par,0,n-1,val[no],1);
}
else{
ba2[no]=par;
}
for(auto j:adj2[no]){
dfs(j,ba2[no]);
}
}
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);
xa.insert(val[i]);
mm.pb(min(x,y));
}
int ind7=0;
map<int,int> kk;
for(auto j:xa){
kk[j]=ind7;
yy.pb({j,ind7});
ind7++;
}
for(int i=0;i<n;i++){
val[i]=kk[val[i]];
}
for(int i=0;i<n;i++){
cc[i][0]=le[i];
dd[i][0]=re2[i];
adj[dd[i][0]].pb(i);
if(cc[i][0]==-1){
adj2[n].pb(i);
}
else{
adj2[cc[i][0]].pb(i);
}
// cout<<i<<":"<<le[i]<<endl;
// cout<<i<<":"<<re2[i]<<endl;
if(re2[i]==n){
dd[i][0]=-1;
}
}
dfs(n);
dfs2(n);
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());
}
int max_towers(int l, int r, int d) {
if(st==0){
rec(0,n-1);
st=1;
}
int de=yy.size();
for(int j=19;j>=0;j--){
if(de-(1<<j)>=0){
if(yy[de-(1<<j)].a>=d){
de-=(1<<j);
}
}
}
if(de==yy.size()){
return 1;
}
llo low=mm.size();
llo su=0;
for(int i=l;i<=r;i++){
if(val[i]>=de){
su++;
}
}
int ind=find(0,0,n-1,l,r,l);
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){
ind3=ind;
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];
}
}
}
llo zot=query5(ba[ind3],0,n-1,de,n-1);
zot-=query5(ba[re2[ind]],0,n-1,de,n-1);
su-=zot;
ss.pb(ind);
}
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);
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];
}
}
}
llo zot=query5(ba2[ind3],0,n-1,de,n-1);
if(cc[ind][0]==-1){
zot-=query5(ba2[n],0,n-1,de,n-1);
}
else{
zot-=query5(ba2[cc[ind][0]],0,n-1,de,n-1);
}
su-=zot;
/* 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]>=de){
su--;
}
}*/
/* for(auto j:tt){
if(val[j]>=de){
su--;
}
}*/
if(ll.a>=0 and rr.a>=0){
if(rr.b==ind2 and ll.b==ind2){
if(val[rr.b]>=de){
su--;
}
}
}
su++;
return su;
}
Compilation message
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:344:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
344 | if(de==yy.size()){
| ~~^~~~~~~~~~~
towers.cpp:348:6: warning: unused variable 'low' [-Wunused-variable]
348 | llo low=mm.size();
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
261 ms |
282856 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5200 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 |
3 ms |
5200 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 |
2683 ms |
74196 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 |
761 ms |
17360 KB |
Output is correct |
| 2 |
Execution timed out |
4056 ms |
96012 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5200 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 |
Runtime error |
261 ms |
282856 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
