#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int imp[100010];
int pri[100010];
ll ans[100010];
int in;
int data[100010];
int bck;
struct qr{int ind,l,r; } query[100010];
bool comp(const qr& a,const qr& b) { return a.l/bck==b.l/bck?a.r<b.r:a.l<b.l;}
int n,q;
ll tree[262144];
inline void add(int ind,int val){
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-1]=data[i];
bck=300;
sort(imp,imp+n);in=unique(imp,imp+n)-imp;
for(i=1;i<=n;++i) pri[i]=lower_bound(imp,imp+in,data[i])-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,comp);
int l=query[0].l, r=query[0].r;
for(i=l;i<=r;++i) add(pri[i],data[i]);
ans[query[0].ind]=tree[1];
for(i=1;i<q;++i){
while(query[i].l<=l-1) --l,add(pri[l],data[l]);
while(r+1<=query[i].r) ++r,add(pri[r],data[r]);
while(l<query[i].l) add(pri[l],-data[l]),++l;
while(query[i].r<r) add(pri[r],-data[r]),--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 |
6260 KB |
Output is correct |
| 2 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 3 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 4 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 5 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 6 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 7 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 8 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 9 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6260 KB |
Output is correct |
| 11 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 12 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 13 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 14 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 15 |
Correct |
0 ms |
6260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6260 KB |
Output is correct |
| 3 |
Correct |
6 ms |
6260 KB |
Output is correct |
| 4 |
Correct |
12 ms |
6260 KB |
Output is correct |
| 5 |
Correct |
26 ms |
6260 KB |
Output is correct |
| 6 |
Correct |
43 ms |
6260 KB |
Output is correct |
| 7 |
Correct |
40 ms |
6260 KB |
Output is correct |
| 8 |
Correct |
43 ms |
6260 KB |
Output is correct |
| 9 |
Correct |
44 ms |
6260 KB |
Output is correct |
| 10 |
Correct |
42 ms |
6260 KB |
Output is correct |
| 11 |
Correct |
43 ms |
6260 KB |
Output is correct |
| 12 |
Correct |
43 ms |
6260 KB |
Output is correct |
| 13 |
Correct |
43 ms |
6260 KB |
Output is correct |
| 14 |
Correct |
43 ms |
6260 KB |
Output is correct |
| 15 |
Correct |
43 ms |
6260 KB |
Output is correct |
| 16 |
Correct |
44 ms |
6260 KB |
Output is correct |
| 17 |
Correct |
47 ms |
6260 KB |
Output is correct |
| 18 |
Correct |
43 ms |
6260 KB |
Output is correct |
| 19 |
Correct |
43 ms |
6260 KB |
Output is correct |
| 20 |
Correct |
44 ms |
6260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 2 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 3 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 4 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 5 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 6 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 7 |
Correct |
0 ms |
6260 KB |
Output is correct |
| 8 |
Correct |
7 ms |
6260 KB |
Output is correct |
| 9 |
Correct |
11 ms |
6260 KB |
Output is correct |
| 10 |
Correct |
19 ms |
6260 KB |
Output is correct |
| 11 |
Correct |
95 ms |
6260 KB |
Output is correct |
| 12 |
Correct |
46 ms |
6260 KB |
Output is correct |
| 13 |
Correct |
67 ms |
6260 KB |
Output is correct |
| 14 |
Correct |
99 ms |
6260 KB |
Output is correct |
| 15 |
Correct |
146 ms |
6260 KB |
Output is correct |
| 16 |
Correct |
77 ms |
6260 KB |
Output is correct |
| 17 |
Correct |
48 ms |
6260 KB |
Output is correct |
| 18 |
Correct |
97 ms |
6260 KB |
Output is correct |
| 19 |
Correct |
90 ms |
6260 KB |
Output is correct |
| 20 |
Correct |
40 ms |
6260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
6260 KB |
Output is correct |
| 2 |
Correct |
232 ms |
6260 KB |
Output is correct |
| 3 |
Correct |
431 ms |
6260 KB |
Output is correct |
| 4 |
Correct |
670 ms |
6260 KB |
Output is correct |
| 5 |
Correct |
964 ms |
6260 KB |
Output is correct |
| 6 |
Correct |
1250 ms |
6260 KB |
Output is correct |
| 7 |
Correct |
1612 ms |
6260 KB |
Output is correct |
| 8 |
Correct |
2104 ms |
6260 KB |
Output is correct |
| 9 |
Correct |
2759 ms |
6260 KB |
Output is correct |
| 10 |
Correct |
3301 ms |
6260 KB |
Output is correct |
| 11 |
Correct |
3161 ms |
6260 KB |
Output is correct |
| 12 |
Correct |
2934 ms |
6260 KB |
Output is correct |
| 13 |
Correct |
2973 ms |
6260 KB |
Output is correct |
| 14 |
Correct |
3281 ms |
6260 KB |
Output is correct |
| 15 |
Correct |
3366 ms |
6260 KB |
Output is correct |
| 16 |
Correct |
3331 ms |
6260 KB |
Output is correct |
| 17 |
Correct |
3332 ms |
6260 KB |
Output is correct |
| 18 |
Correct |
3283 ms |
6260 KB |
Output is correct |
| 19 |
Correct |
3285 ms |
6260 KB |
Output is correct |
| 20 |
Correct |
3275 ms |
6260 KB |
Output is correct |
| 21 |
Correct |
3250 ms |
6260 KB |
Output is correct |
| 22 |
Correct |
3223 ms |
6260 KB |
Output is correct |
| 23 |
Correct |
3185 ms |
6260 KB |
Output is correct |
| 24 |
Correct |
3178 ms |
6260 KB |
Output is correct |
| 25 |
Correct |
3299 ms |
6260 KB |
Output is correct |
