#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
os << '{';
for(int i=0;i<sz(a);i++)
{
if(i>0&&i<sz(a))
os << ", ";
os << a[i];
}
os << '}';
return os;
}
struct node{
int l;
int r;
int best;
int num;
ll sum;
node* left;
node* right;
node(int le,int ri)
{
l=le;
r=ri;
best=0;
sum=0;
num=1;
left=right=NULL;
}
void extend()
{
if(left!=NULL)
return;
int m=(l+r)>>1;
left=new node(l,m);
right=new node(m+1,r);
}
void prop()
{
if(best==0)
return;
if(left->best==best)
{
left->sum+=sum;
left->num+=num;
}
if(left->best<best)
{
left->sum=sum;
left->best=best;
left->num=num;
}
if(right->best==best)
{
right->sum+=sum;
right->num+=num;
}
if(right->best<best)
{
right->sum=sum;
right->best=best;
right->num=num;
}
sum=0;
best=0;
num=0;
}
void add(int qs,int qe,int b,ll s,int n)
{
if(qs>r||qe<l)
return;
if(qs<=l&&qe>=r)
{
if(b==best)
{
sum+=s;
num+=n;
}
if(b>best)
{
best=b;
sum=s;
num=n;
}
return;
}
extend();
prop();
left->add(qs,qe,b,s,n);
right->add(qs,qe,b,s,n);
}
tuple<int,int,ll> get(int pos)
{
if(l==r)
return make_tuple(best,num,sum);
if(left==NULL)
return make_tuple(best,num,sum);
extend();
prop();
int m=(l+r)>>1;
if(pos<=m)
return left->get(pos);
return right->get(pos);
}
};
int main()
{
int n;
scanf("%i",&n);
vector<int> niz(n),niz1(n);
for(int i=0;i<n;i++)
scanf("%i",&niz1[i]);
vector<int> ss=niz1;
sort(all(ss));
ss.erase(unique(all(ss)),ss.end());
map<int,int> mapa;
for(int i=0;i<ss.size();i++)
mapa[ss[i]]=i;
for(int i=0;i<n;i++)
{
niz.pb(mapa[niz1[i]]);
}
int N=ss.size();
deque<int> q;
q.pb(niz[0]);
int minn=niz[0],maxx=niz[0];
for(int i=1;i<n;i++)
{
if(niz[i]<minn)
{
minn=niz[i];
q.push_front(niz[i]);
continue;
}
if(niz[i]>maxx)
{
maxx=niz[i];
q.push_back(niz[i]);
continue;
}
node f(0,N);
int be=0;
ll s=0;
int nu=0;
for(auto p:q)
{
int best,num;
ll sum;
tie(best,num,sum)=f.get(p);
best++;
sum+=(ll)num*p;
f.add(p+1,N,best,sum,num);
if(be==best)
s+=sum,nu+=num;
if(be<best)
{
be=best;
s=sum;
nu=num;
}
}
for(int j=i;j<n;j++)
{
int p=niz[j];
int best,num;
ll sum;
tie(best,num,sum)=f.get(p);
best++;
sum+=(ll)num*p;
f.add(p+1,N,best,sum,num);
if(be==best)
s+=sum,nu+=num;
if(be<best)
{
be=best;
s=sum;
nu=num;
}
}
node b(0,N);
for(int j=n-1;j>=i;j--)
{
int p=niz[j];
int best,num;
ll sum;
tie(best,num,sum)=b.get(p);
best++;
sum+=(ll)num*p;
b.add(p+1,N,best,sum,num);
if(be==best)
s+=sum,nu+=num;
if(be<best)
{
be=best;
s=sum;
nu=num;
}
}
for(auto p:q)
{
int best,num;
ll sum;
tie(best,num,sum)=b.get(p);
best++;
sum+=(ll)num*p;
b.add(p+1,N,best,sum,num);
if(be==best)
s+=sum,nu+=num;
if(be<best)
{
be=best;
s=sum;
nu=num;
}
}
printf("%i %i\n",be,nu);
return 0;
}
printf("%i %i\n",n,1);
return 0;
node f(0,1e9),b(0,1e9);
int be=0;
ll s=0;
int nu=0;
for(int i=0;i<n;i++)
{
int best,num;
ll sum;
tie(best,num,sum)=f.get(niz[i]);
best++;
sum+=(ll)num*niz[i];
f.add(niz[i]+1,1e9,best,sum,num);
if(be==best)
s+=sum,nu+=num;
if(be<best)
{
be=best;
s=sum;
nu=num;
}
}
printf("%i %i %lld\n",be,nu,s);
return 0;
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:135:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ss.size();i++)
~^~~~~~~~~~
zoltan.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
zoltan.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&niz1[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
252 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
256 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 11 |
Incorrect |
166 ms |
11480 KB |
Output isn't correct |
| 12 |
Incorrect |
141 ms |
10048 KB |
Output isn't correct |
| 13 |
Incorrect |
136 ms |
9344 KB |
Output isn't correct |
| 14 |
Incorrect |
192 ms |
10424 KB |
Output isn't correct |
| 15 |
Incorrect |
251 ms |
12708 KB |
Output isn't correct |
| 16 |
Incorrect |
277 ms |
14828 KB |
Output isn't correct |
| 17 |
Incorrect |
196 ms |
12664 KB |
Output isn't correct |
| 18 |
Incorrect |
207 ms |
12672 KB |
Output isn't correct |
| 19 |
Incorrect |
203 ms |
12664 KB |
Output isn't correct |
| 20 |
Incorrect |
205 ms |
12636 KB |
Output isn't correct |
