#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define mid ((l+r)>>1)
const int sq = 400;
inline int64_t hilbertOrder(int x, int y, int pow, int rotate) {
if (pow == 0) {
return 0;
}
int hpow = 1 << (pow-1);
int seg = (x < hpow) ? (
(y < hpow) ? 0 : 3
) : (
(y < hpow) ? 1 : 2
);
seg = (seg + rotate) & 3;
const int rotateDelta[4] = {3, 0, 0, 1};
int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
int nrot = (rotate + rotateDelta[seg]) & 3;
int64_t subSquareSize = int64_t(1) << (2*pow - 2);
int64_t ans = seg * subSquareSize;
int64_t add = hilbertOrder(nx, ny, pow-1, nrot);
ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
return ans;
}
struct query{
int l, r, id;
long long order;
void init(){
order = hilbertOrder(l, r, 21, 0);
}
bool operator < (const query &o) const{
return order < o.order;
}
}q[100100];
int n, m, cnt, k[100100], to[100100];
ll x[100100], tree[400400], ans[100100];
map<ll, int> mp;
void init(int node = 1, int l = 1, int r = cnt){
if(l == r){
to[l] = node;
return;
}
init(node*2, l, mid), init(node*2+1, mid+1, r);
}
void update(int id, ll val){
tree[id] += val;
id /= 2;
while(id){
tree[id] = max(tree[id*2], tree[id*2+1]);
id /= 2;
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> x[i], mp[x[i]] = 0;
for(auto &x : mp) x.second = ++cnt;
init();
for(int i=1;i<=n;i++) k[i] = to[mp[x[i]]];
for(int i=1;i<=m;i++) cin >> q[i].l >> q[i].r, q[i].id = i, q[i].init();
sort(q+1, q+1+m);
int l = q[1].l, r = q[1].l-1;
for(int i=1;i<=m;i++){
while(l > q[i].l) l--, update(k[l], x[l]);
while(r < q[i].r) r++, update(k[r], x[r]);
while(l < q[i].l) update(k[l], -x[l]), l++;
while(r > q[i].r) update(k[r], -x[r]), r--;
ans[q[i].id] = tree[1];
}
for(int i=1;i<=m;i++) cout << ans[i] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
7 ms |
512 KB |
Output is correct |
5 |
Correct |
11 ms |
640 KB |
Output is correct |
6 |
Correct |
15 ms |
640 KB |
Output is correct |
7 |
Correct |
16 ms |
768 KB |
Output is correct |
8 |
Correct |
13 ms |
640 KB |
Output is correct |
9 |
Correct |
14 ms |
640 KB |
Output is correct |
10 |
Correct |
19 ms |
768 KB |
Output is correct |
11 |
Correct |
19 ms |
768 KB |
Output is correct |
12 |
Correct |
19 ms |
768 KB |
Output is correct |
13 |
Correct |
19 ms |
768 KB |
Output is correct |
14 |
Correct |
18 ms |
768 KB |
Output is correct |
15 |
Correct |
18 ms |
768 KB |
Output is correct |
16 |
Correct |
14 ms |
640 KB |
Output is correct |
17 |
Correct |
11 ms |
640 KB |
Output is correct |
18 |
Correct |
18 ms |
768 KB |
Output is correct |
19 |
Correct |
20 ms |
768 KB |
Output is correct |
20 |
Correct |
18 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
9 ms |
640 KB |
Output is correct |
8 |
Correct |
11 ms |
768 KB |
Output is correct |
9 |
Correct |
20 ms |
1280 KB |
Output is correct |
10 |
Correct |
13 ms |
1024 KB |
Output is correct |
11 |
Correct |
91 ms |
4728 KB |
Output is correct |
12 |
Correct |
39 ms |
1536 KB |
Output is correct |
13 |
Correct |
96 ms |
2936 KB |
Output is correct |
14 |
Correct |
151 ms |
7416 KB |
Output is correct |
15 |
Correct |
174 ms |
10488 KB |
Output is correct |
16 |
Correct |
161 ms |
12280 KB |
Output is correct |
17 |
Correct |
48 ms |
2680 KB |
Output is correct |
18 |
Correct |
85 ms |
4472 KB |
Output is correct |
19 |
Correct |
149 ms |
13560 KB |
Output is correct |
20 |
Correct |
80 ms |
11000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
888 KB |
Output is correct |
2 |
Correct |
95 ms |
1528 KB |
Output is correct |
3 |
Correct |
210 ms |
2420 KB |
Output is correct |
4 |
Correct |
336 ms |
3576 KB |
Output is correct |
5 |
Correct |
469 ms |
4344 KB |
Output is correct |
6 |
Correct |
548 ms |
4216 KB |
Output is correct |
7 |
Correct |
506 ms |
4348 KB |
Output is correct |
8 |
Correct |
442 ms |
4984 KB |
Output is correct |
9 |
Correct |
375 ms |
5496 KB |
Output is correct |
10 |
Correct |
231 ms |
5752 KB |
Output is correct |
11 |
Correct |
435 ms |
5752 KB |
Output is correct |
12 |
Correct |
810 ms |
5880 KB |
Output is correct |
13 |
Correct |
1172 ms |
6368 KB |
Output is correct |
14 |
Correct |
1402 ms |
10496 KB |
Output is correct |
15 |
Correct |
1626 ms |
12652 KB |
Output is correct |
16 |
Correct |
1653 ms |
11800 KB |
Output is correct |
17 |
Correct |
1453 ms |
11512 KB |
Output is correct |
18 |
Correct |
1423 ms |
11248 KB |
Output is correct |
19 |
Correct |
1432 ms |
11132 KB |
Output is correct |
20 |
Correct |
1366 ms |
10496 KB |
Output is correct |
21 |
Correct |
1387 ms |
10288 KB |
Output is correct |
22 |
Correct |
1398 ms |
10296 KB |
Output is correct |
23 |
Correct |
1419 ms |
10104 KB |
Output is correct |
24 |
Correct |
1374 ms |
10064 KB |
Output is correct |
25 |
Correct |
181 ms |
8276 KB |
Output is correct |