#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int imp[100010];
typedef long long ll;
ll ans[100010];
int in;
int data[100010];
int bck;
struct qr{int ind,l,r; bool operator<(const qr& other) const { return l/bck==other.l/bck?r<other.r:l<other.l; }; } query[100010];
int n,q;
ll tree[262144];
void add(int val){
int ind=lower_bound(imp,imp+in,val)-imp;
ind+=131072;
tree[ind]+=val;
ind/=2;
while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
}
void rem(int val){
int ind=lower_bound(imp,imp+in,val)-imp;
ind+=131072;
tree[ind]-=val;
ind/=2;
while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
}
int main()
{
scanf("%d%d",&n,&q); int i; for(i=1;i<=n;++i) scanf("%d",data+i),imp[i]=data[i];
bck=n/sqrt(q);
sort(imp,imp+n);in=unique(imp,imp+n)-imp;
int a,b;
for(i=0;i<q;++i) scanf("%d%d",&a,&b),query[i].ind=i,query[i].l=a,query[i].r=b;
sort(query,query+q);
int l=query[0].l, r=query[0].r;
for(i=l;i<=r;++i) add(data[i]);
ans[query[0].ind]=tree[1];
for(i=1;i<q;++i){
while(query[i].l<=l-1) add(data[--l]);
while(r+1<=query[i].r) add(data[++r]);
while(l<query[i].l) rem(data[l++]);
while(query[i].r<r) rem(data[r--]);
ans[query[i].ind]=tree[1];
}
for(i=0;i<q;++i) printf("%lld\n",ans[i]);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 3 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 4 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 5 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 6 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 7 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 8 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 9 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 10 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 11 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 12 |
Correct |
1 ms |
5892 KB |
Output is correct |
| 13 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 14 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 15 |
Correct |
0 ms |
5892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5892 KB |
Output is correct |
| 4 |
Correct |
11 ms |
5892 KB |
Output is correct |
| 5 |
Correct |
27 ms |
5892 KB |
Output is correct |
| 6 |
Correct |
55 ms |
5892 KB |
Output is correct |
| 7 |
Correct |
60 ms |
5892 KB |
Output is correct |
| 8 |
Correct |
49 ms |
5892 KB |
Output is correct |
| 9 |
Correct |
49 ms |
5892 KB |
Output is correct |
| 10 |
Correct |
73 ms |
5892 KB |
Output is correct |
| 11 |
Correct |
72 ms |
5892 KB |
Output is correct |
| 12 |
Correct |
72 ms |
5892 KB |
Output is correct |
| 13 |
Correct |
71 ms |
5892 KB |
Output is correct |
| 14 |
Correct |
69 ms |
5892 KB |
Output is correct |
| 15 |
Correct |
72 ms |
5892 KB |
Output is correct |
| 16 |
Correct |
50 ms |
5892 KB |
Output is correct |
| 17 |
Correct |
44 ms |
5892 KB |
Output is correct |
| 18 |
Correct |
67 ms |
5892 KB |
Output is correct |
| 19 |
Correct |
73 ms |
5892 KB |
Output is correct |
| 20 |
Correct |
75 ms |
5892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5892 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 3 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 4 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5892 KB |
Output is correct |
| 6 |
Correct |
0 ms |
5892 KB |
Output is correct |
| 7 |
Correct |
4 ms |
5892 KB |
Output is correct |
| 8 |
Correct |
8 ms |
5892 KB |
Output is correct |
| 9 |
Correct |
14 ms |
5892 KB |
Output is correct |
| 10 |
Correct |
18 ms |
5892 KB |
Output is correct |
| 11 |
Correct |
94 ms |
5892 KB |
Output is correct |
| 12 |
Correct |
41 ms |
5892 KB |
Output is correct |
| 13 |
Correct |
73 ms |
5892 KB |
Output is correct |
| 14 |
Correct |
111 ms |
5892 KB |
Output is correct |
| 15 |
Correct |
130 ms |
5892 KB |
Output is correct |
| 16 |
Incorrect |
91 ms |
5892 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
5892 KB |
Output is correct |
| 2 |
Correct |
524 ms |
5892 KB |
Output is correct |
| 3 |
Correct |
1142 ms |
5892 KB |
Output is correct |
| 4 |
Correct |
1923 ms |
5892 KB |
Output is correct |
| 5 |
Correct |
2798 ms |
5892 KB |
Output is correct |
| 6 |
Correct |
3234 ms |
5892 KB |
Output is correct |
| 7 |
Correct |
3262 ms |
5892 KB |
Output is correct |
| 8 |
Correct |
3059 ms |
5892 KB |
Output is correct |
| 9 |
Correct |
3345 ms |
5892 KB |
Output is correct |
| 10 |
Correct |
3362 ms |
5892 KB |
Output is correct |
| 11 |
Correct |
3852 ms |
5892 KB |
Output is correct |
| 12 |
Execution timed out |
4000 ms |
5888 KB |
Program timed out |
| 13 |
Halted |
0 ms |
0 KB |
- |
