#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; ///find_by_order(),order_of_key()
int n;
struct segmentTree{
vector<pair<int,int> > lazy;
void init()
{
lazy.resize(4*n);
}
void prop(int i)
{
lazy[2*i]=lazy[i];
lazy[2*i+1]=lazy[i];
}
void set(int l,int r,pair<int,int> x,int i=1,int lo=0,int hi=n-1)
{
//printf("Usao za %i-%i %i %i-%i\n",l,r,i,lo,hi);
if(hi<l||lo>r)
return;
if(l<=lo&&hi<=r)
{
lazy[i]=x;
return;
}
prop(i);
int mid=(lo+hi)/2;
set(l,r,x,2*i,lo,mid);
set(l,r,x,2*i+1,mid+1,hi);
}
pair<int,int> get(int p,int i=1,int lo=0,int hi=n-1)
{
if(lo>p||hi<p)
return make_pair(0,0);
if(lo==hi&&lo==p)
return lazy[i];
prop(i);
int mid=(lo+hi)/2;
pair<int,int> p1=get(p,2*i,lo,mid),p2=get(p,2*i+1,mid+1,hi);
return make_pair(p1.first+p2.first,p1.second+p2.second);
}
} ST,ST2;
/// pair<int,int> f1 - first:height, second: start position
bool test(pair<int,int> f1,pair<int,int> f2,int poz)
{
double h1=f1.first+(double)sqrt(abs(f1.second-poz));
double h2=f2.first+(double)sqrt(abs(f2.second-poz));
return h1>h2;
}
int calc(pair<int,int> f,int poz)
{
int dist=abs(f.second-poz);
//printf("Dist: %i\n",dist);
double r = f.first+(double)sqrt(dist);
int res=r;
if(r>res)
res++;
//printf("Vracam %i:\n",res);
return res;
}
int main()
{
scanf("%i",&n);
ST.init();
ST2.init();
vector<int> arr(n);
for(int i=0;i<n;i++)
{
scanf("%i",&arr[i]);
}
int maxx=-1;
for(int i=0;i<n;i++)
{
if(arr[i]>maxx)
{
//printf("Usao za %i\n",i);
maxx=arr[i];
pair<int,int> tr=make_pair(arr[i],i);
int l=i,r=n-1;
while(l<r)
{
int mid=(l+r)/2;
pair<int,int> f=ST.get(mid);
if(test(f,tr,mid))
{
l=mid+1;
}
else
{
r=mid;
}
}
if(l==n-1)
{
pair<int,int> f=ST.get(l);
if(test(f,tr,l))
{
continue;
}
}
//printf("Postavljam od %i do %i na %i-%i\n",l,n-1,tr.first,tr.second);
ST.set(l,n-1,tr);
}
}
//printf("Zavrxio\n");
maxx=-1;
for(int i=n-1;i>=0;i--)
{
if(arr[i]>maxx)
{
//printf("Usao za %i\n",i);
maxx=arr[i];
pair<int,int> tr=make_pair(arr[i],i);
int l=0,r=i;
while(l<r)
{
int mid=(l+r)/2;
pair<int,int> f=ST2.get(mid);
if(test(f,tr,mid))
{
r=mid;
}
else
{
l=mid+1;
}
}
if(l==0)
{
pair<int,int> f=ST2.get(l);
//printf("%i %i\n",f.first,f.second);
if(test(f,tr,l))
{
continue;
}
}
//printf("Postavljam %i-%i na %i %i\n",0,l,tr.first,tr.second);
ST2.set(0,l,tr);
}
}
for(int i=0;i<n;i++)
{
pair<int,int> f1=ST.get(i);
pair<int,int> f2=ST2.get(i);
//printf("F1: %i %i, F2: %i %i\n",f1.first,f1.second,f2.first,f2.second);
int m=max(calc(f1,i),calc(f2,i));
printf("%i\n",m-arr[i]);
}
return 0;
}
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; ///find_by_order(),order_of_key()
int n;
struct segmentTree{
vector<pair<int,int> > lazy;
void init()
{
lazy.resize(4*n);
}
void prop(int i)
{
lazy[2*i]=lazy[i];
lazy[2*i+1]=lazy[i];
}
void set(int l,int r,pair<int,int> x,int i=1,int lo=0,int hi=n-1)
{
//printf("Usao za %i-%i %i %i-%i\n",l,r,i,lo,hi);
if(hi<l||lo>r)
return;
if(l<=lo&&hi<=r)
{
lazy[i]=x;
return;
}
prop(i);
int mid=(lo+hi)/2;
set(l,r,x,2*i,lo,mid);
set(l,r,x,2*i+1,mid+1,hi);
}
pair<int,int> get(int p,int i=1,int lo=0,int hi=n-1)
{
if(lo>p||hi<p)
return make_pair(0,0);
if(lo==hi&&lo==p)
return lazy[i];
prop(i);
int mid=(lo+hi)/2;
pair<int,int> p1=get(p,2*i,lo,mid),p2=get(p,2*i+1,mid+1,hi);
return make_pair(p1.first+p2.first,p1.second+p2.second);
}
} ST,ST2;
/// pair<int,int> f1 - first:height, second: start position
bool test(pair<int,int> f1,pair<int,int> f2,int poz)
{
double h1=f1.first+(double)sqrt(abs(f1.second-poz));
double h2=f2.first+(double)sqrt(abs(f2.second-poz));
return h1>h2;
}
int calc(pair<int,int> f,int poz)
{
int dist=abs(f.second-poz);
//printf("Dist: %i\n",dist);
double r = f.first+(double)sqrt(dist);
int res=r;
if(r>res)
res++;
//printf("Vracam %i:\n",res);
return res;
}
int main()
{
scanf("%i",&n);
ST.init();
ST2.init();
vector<int> arr(n);
for(int i=0;i<n;i++)
{
scanf("%i",&arr[i]);
}
int maxx=-1;
for(int i=0;i<n;i++)
{
if(arr[i]>maxx)
{
//printf("Usao za %i\n",i);
maxx=arr[i];
pair<int,int> tr=make_pair(arr[i],i);
int l=i,r=n-1;
while(l<r)
{
int mid=(l+r)/2;
pair<int,int> f=ST.get(mid);
if(test(f,tr,mid))
{
l=mid+1;
}
else
{
r=mid;
}
}
if(l==n-1)
{
pair<int,int> f=ST.get(l);
if(test(f,tr,l))
{
continue;
}
}
//printf("Postavljam od %i do %i na %i-%i\n",l,n-1,tr.first,tr.second);
ST.set(l,n-1,tr);
}
}
//printf("Zavrxio\n");
maxx=-1;
for(int i=n-1;i>=0;i--)
{
if(arr[i]>maxx)
{
//printf("Usao za %i\n",i);
maxx=arr[i];
pair<int,int> tr=make_pair(arr[i],i);
int l=0,r=i;
while(l<r)
{
int mid=(l+r)/2;
pair<int,int> f=ST2.get(mid);
if(test(f,tr,mid))
{
r=mid;
}
else
{
l=mid+1;
}
}
if(l==0)
{
pair<int,int> f=ST2.get(l);
//printf("%i %i\n",f.first,f.second);
if(test(f,tr,l))
{
continue;
}
}
//printf("Postavljam %i-%i na %i %i\n",0,l,tr.first,tr.second);
ST2.set(0,l,tr);
}
}
for(int i=0;i<n;i++)
{
pair<int,int> f1=ST.get(i);
pair<int,int> f2=ST2.get(i);
//printf("F1: %i %i, F2: %i %i\n",f1.first,f1.second,f2.first,f2.second);
int m=max(calc(f1,i),calc(f2,i));
printf("%i\n",m-arr[i]);
}
return 0;
}
Compilation message
pio.cpp:171:5: error: redefinition of 'int n'
int n;
^
pio.cpp:12:5: note: 'int n' previously declared here
int n;
^
pio.cpp:172:8: error: redefinition of 'struct segmentTree'
struct segmentTree{
^~~~~~~~~~~
pio.cpp:13:8: note: previous definition of 'struct segmentTree'
struct segmentTree{
^~~~~~~~~~~
pio.cpp:210:3: error: conflicting declaration 'int ST'
} ST,ST2;
^~
pio.cpp:51:3: note: previous declaration as 'segmentTree ST'
} ST,ST2;
^~
pio.cpp:210:6: error: conflicting declaration 'int ST2'
} ST,ST2;
^~~
pio.cpp:51:6: note: previous declaration as 'segmentTree ST2'
} ST,ST2;
^~~
pio.cpp: In function 'bool test(std::pair<int, int>, std::pair<int, int>, int)':
pio.cpp:212:6: error: redefinition of 'bool test(std::pair<int, int>, std::pair<int, int>, int)'
bool test(pair<int,int> f1,pair<int,int> f2,int poz)
^~~~
pio.cpp:53:6: note: 'bool test(std::pair<int, int>, std::pair<int, int>, int)' previously defined here
bool test(pair<int,int> f1,pair<int,int> f2,int poz)
^~~~
pio.cpp: In function 'int calc(std::pair<int, int>, int)':
pio.cpp:218:5: error: redefinition of 'int calc(std::pair<int, int>, int)'
int calc(pair<int,int> f,int poz)
^~~~
pio.cpp:59:5: note: 'int calc(std::pair<int, int>, int)' previously defined here
int calc(pair<int,int> f,int poz)
^~~~
pio.cpp: In function 'int main()':
pio.cpp:229:5: error: redefinition of 'int main()'
int main()
^~~~
pio.cpp:70:5: note: 'int main()' previously defined here
int main()
^~~~
pio.cpp: In function 'int main()':
pio.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
pio.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&arr[i]);
~~~~~^~~~~~~~~~~~~~
pio.cpp: In function 'int main()':
pio.cpp:231:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
pio.cpp:237:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&arr[i]);
~~~~~^~~~~~~~~~~~~~
