This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int n, q, i, j, k, a, b, B, inv[100010], A[100010], cnt[100010];
vector<int>comp;
long long ans[100010], seg[400010];
struct query
{
int i, l, r;
};
vector<query>Q;
bool cmp(query a, query b)
{
if(a.l/B==b.l/B)return a.r<b.r;
else return a.l/B<b.l/B;
}
void update(int x, long long v)
{
x+=n;seg[x]=v;
for(;x>1;x>>=1)seg[x>>1]=max(seg[x], seg[x^1]);
}
void add(int i)
{
cnt[A[i]]++;
update(A[i], 1LL*cnt[A[i]]*inv[A[i]]);
}
void del(int i)
{
cnt[A[i]]--;
update(A[i], 1LL*cnt[A[i]]*inv[A[i]]);
}
main()
{
for(scanf("%d %d", &n, &q);i++<n;)
{
scanf("%d", &A[i]);
comp.push_back(A[i]);
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
for(i=0;i++<n;)
{
a=lower_bound(comp.begin(), comp.end(), A[i])-comp.begin()+1;
inv[a]=A[i];
A[i]=a;
}
B=(int)sqrt(n);
for(i=0;i++<q;)
{
scanf("%d %d", &a, &b);
Q.push_back({i, a, b});
}
sort(Q.begin(), Q.end(), cmp);
for(i=Q[0].l;i<=Q[0].r;i++)add(i);
ans[Q[0].i]=seg[1];
for(i=1;i<q;i++)
{
if(Q[i].l<Q[i-1].l)for(j=Q[i-1].l-1;j>=Q[i].l;j--)add(j);
else for(j=Q[i-1].l;j<Q[i].l;j++)del(j);
if(Q[i].r>Q[i-1].r)for(j=Q[i-1].r+1;j<=Q[i].r;j++)add(j);
else for(j=Q[i-1].r;j>Q[i].r;j--)del(j);
ans[Q[i].i]=seg[1];
}
for(i=0;i++<q;)printf("%lld\n", ans[i]);
}
Compilation message (stderr)
historic.cpp:31:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
31 | main()
| ^~~~
historic.cpp: In function 'int main()':
historic.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | for(scanf("%d %d", &n, &q);i++<n;)
| ~~~~~^~~~~~~~~~~~~~~~~
historic.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | scanf("%d", &A[i]);
| ~~~~~^~~~~~~~~~~~~
historic.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |