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;
#define bit(n,i) ((n>>i)&1)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second
#define ll long long
#define debug(x) cerr << #x << ' ' << x << '\n'
#define dbg(x) cerr<<#x<<' '<<x<<' '
const int base=31;
const int MOD=1e9+7;
const int N=1e5+5;
const int B=sqrt(N);
vector<int>f;
int n,q,a[N],timeDfs;
pii mp[N];
ll cur=0,pre=0;
void add(int x)
{
if (mp[x].fi!=timeDfs)
{
mp[x]={timeDfs,0};
}
mp[x].se++;
cur=max(cur,1ll*f[x]*mp[x].se);
}
void erase(int x)
{
mp[x].se--;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Shiho
freopen("izumi_shiho_supremacy.in","r", stdin);
freopen("izumi_shiho_supremacy.out","w", stdout);
#endif
cin>>n>>q;
for (int i=1;i<=n;i++)
{
cin>>a[i];
f.pb(a[i]);
}
sort(all(f));
f.erase(unique(all(f)),f.end());
for (int i=1;i<=n;i++) a[i]=lower_bound(all(f),a[i])-f.begin();
vector<ll>ans(q);
vector<array<int,3>>queries(q);
for (int i=0;i<q;i++)
{
int l,r;
cin>>l>>r;
queries[i]={l,r,i};
}
sort(all(queries),[&](array<int,3>x,array<int,3>y){
if (x[0]/B!=y[0]/B) return x[0]<y[0];
return x[1]<y[1];
});
int preblock=-1;
int preR=-1;
for (auto [l,r,id]:queries)
{
int idL=l/B;
int idR=r/B;
if (idL!=preblock)
{
++timeDfs;
preblock=idL;
pre=cur=0;
preR=(idL+1)*B;
}
if (idL==idR)
{
pre=cur;
for (int i=l;i<=r;i++) add(a[i]);
ans[id]=cur;
cur=pre;
for (int i=l;i<=r;i++) erase(a[i]);
}
else
{
for (;preR<=r;preR++) add(a[preR]);
pre=cur;
for (int i=l;i<=(idL+1)*B-1;i++) add(a[i]);
ans[id]=cur;
cur=pre;
for (int i=l;i<=(idL+1)*B-1;i++) erase(a[i]);
}
}
for (int i=0;i<q;i++) cout<<ans[i]<<"\n";
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
# | 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... |