This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//https://oj.uz/problem/view/JOI14_historical
#include<bits/stdc++.h>
const int N = 1e5 + 5;
const int MAGIC = 300;
using namespace std;
vector <int> Query[N/MAGIC + 5];
int n, q, a[N], l[N], r[N], p[N], x[N], cnt[N];
long long ans[N];
bool cmp(int a, int b){return r[a] < r[b];}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) x[i] = i;
sort(x, x+n, [](int xx, int yy){return a[xx] < a[yy];});
for (int i = 0; i < n; i++){
if (i == 0) p[x[i]] = 1;
else p[x[i]] = p[x[i-1]] + (a[x[i]] != a[x[i-1]]);
}
for (int i = 1; i <= q; i++){
cin >> l[i] >> r[i]; l[i]--; r[i]--;
Query[l[i]/MAGIC].push_back(i);
}
for (int i = 0; i <= n/MAGIC; i++) sort(Query[i].begin(), Query[i].end(), cmp);
for (int i = 0; i <= n/MAGIC; i++){
int R = (i+1)*MAGIC-1;
long long Max = 0;
memset(cnt, 0, sizeof cnt);
for (int j = 0; j < Query[i].size(); j++){
int id = Query[i][j], x = l[id], y = r[id];
if (y < R){
for (int k = y; k >= x; k--) cnt[p[k]]++, ans[id] = max(ans[id], 1LL * cnt[p[k]] * a[k]);
for (int k = y; k >= x; k--) cnt[p[k]]--;
continue;
}
while (R < y) R++, cnt[p[R]]++, Max = max(Max, 1LL * cnt[p[R]] * a[R]); ans[id] = Max;
for (int k = (i+1)*MAGIC-1; k >= x; k--) cnt[p[k]]++, ans[id] = max(ans[id], 1LL * cnt[p[k]] * a[k]);
for (int k = (i+1)*MAGIC-1; k >= x; k--) cnt[p[k]]--;
}
}
for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
Compilation message (stderr)
historic.cpp: In function 'int main()':
historic.cpp:34:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < Query[i].size(); j++){
^
# | 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... |