#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
#define eack emplace_back
#define all(x) (x).begin(), (x).end()
int X[100005], in[100005][2];
vector<int> xx;
const int SIZE = 1 << 17;
struct ST {
long long A[2 * SIZE];
int sz;
void update(int x, long long v) {
x += SIZE; A[x] += v;
for (x >>= 1; x; x >>= 1) A[x] = max(A[x << 1], A[x << 1 | 1]);
}
long long query() { return A[1]; }
} seg;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int N, Q; cin >> N >> Q;
for (int i = 1; i <= N; ++i) cin >> X[i], xx.eack(X[i]);
sort(all(xx));
xx.erase(unique(all(xx)), xx.end());
for (int i = 1; i <= N; ++i) {
X[i] = lower_bound(all(xx), X[i]) - xx.begin();
}
seg.sz = xx.size() - 1;
vector<pair<pii, int> > qry(Q);
vector<long long> ans(Q);
for (int i = 0; i < Q; ++i) {
cin >> in[i][0] >> in[i][1];
qry.eack(pii(in[i][0] / 600, in[i][1]), i);
}
sort(all(qry));
int s = 1, e = 0;
for (auto i : qry) {
int ns = in[i.ss][0], ne = in[i.ss][1];
for (; s < ns; ++s) seg.update(X[s], -xx[X[s]]);
for (; s > ns; --s) seg.update(X[s - 1], xx[X[s - 1]]);
for (; e < ne; ++e) seg.update(X[e + 1], xx[X[e + 1]]);
for (; e > ne; --e) seg.update(X[e], -xx[X[e]]);
ans[i.ss] = seg.query();
}
for (auto i : ans) cout << i << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
3 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
504 KB |
Output is correct |
| 3 |
Correct |
8 ms |
504 KB |
Output is correct |
| 4 |
Correct |
15 ms |
536 KB |
Output is correct |
| 5 |
Correct |
32 ms |
736 KB |
Output is correct |
| 6 |
Correct |
50 ms |
760 KB |
Output is correct |
| 7 |
Correct |
50 ms |
844 KB |
Output is correct |
| 8 |
Correct |
51 ms |
760 KB |
Output is correct |
| 9 |
Correct |
51 ms |
760 KB |
Output is correct |
| 10 |
Correct |
47 ms |
888 KB |
Output is correct |
| 11 |
Correct |
48 ms |
888 KB |
Output is correct |
| 12 |
Correct |
48 ms |
944 KB |
Output is correct |
| 13 |
Correct |
49 ms |
888 KB |
Output is correct |
| 14 |
Correct |
47 ms |
888 KB |
Output is correct |
| 15 |
Correct |
48 ms |
888 KB |
Output is correct |
| 16 |
Correct |
50 ms |
860 KB |
Output is correct |
| 17 |
Correct |
60 ms |
900 KB |
Output is correct |
| 18 |
Correct |
47 ms |
888 KB |
Output is correct |
| 19 |
Correct |
49 ms |
888 KB |
Output is correct |
| 20 |
Correct |
50 ms |
888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
3 ms |
508 KB |
Output is correct |
| 6 |
Correct |
3 ms |
504 KB |
Output is correct |
| 7 |
Correct |
5 ms |
632 KB |
Output is correct |
| 8 |
Correct |
8 ms |
764 KB |
Output is correct |
| 9 |
Correct |
16 ms |
1040 KB |
Output is correct |
| 10 |
Correct |
21 ms |
1272 KB |
Output is correct |
| 11 |
Correct |
79 ms |
6700 KB |
Output is correct |
| 12 |
Correct |
48 ms |
2040 KB |
Output is correct |
| 13 |
Correct |
67 ms |
3572 KB |
Output is correct |
| 14 |
Correct |
93 ms |
5988 KB |
Output is correct |
| 15 |
Correct |
125 ms |
9252 KB |
Output is correct |
| 16 |
Correct |
71 ms |
6824 KB |
Output is correct |
| 17 |
Correct |
38 ms |
3268 KB |
Output is correct |
| 18 |
Correct |
62 ms |
6460 KB |
Output is correct |
| 19 |
Correct |
72 ms |
8776 KB |
Output is correct |
| 20 |
Correct |
39 ms |
4976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
210 ms |
2060 KB |
Output is correct |
| 3 |
Correct |
342 ms |
2968 KB |
Output is correct |
| 4 |
Correct |
534 ms |
3672 KB |
Output is correct |
| 5 |
Correct |
713 ms |
4652 KB |
Output is correct |
| 6 |
Correct |
845 ms |
5432 KB |
Output is correct |
| 7 |
Correct |
983 ms |
6064 KB |
Output is correct |
| 8 |
Correct |
1266 ms |
7152 KB |
Output is correct |
| 9 |
Correct |
1671 ms |
7884 KB |
Output is correct |
| 10 |
Correct |
2070 ms |
8044 KB |
Output is correct |
| 11 |
Correct |
1739 ms |
8136 KB |
Output is correct |
| 12 |
Correct |
1607 ms |
8288 KB |
Output is correct |
| 13 |
Correct |
1637 ms |
8428 KB |
Output is correct |
| 14 |
Correct |
2000 ms |
9060 KB |
Output is correct |
| 15 |
Correct |
2095 ms |
9308 KB |
Output is correct |
| 16 |
Correct |
2056 ms |
9184 KB |
Output is correct |
| 17 |
Correct |
2053 ms |
9056 KB |
Output is correct |
| 18 |
Correct |
2028 ms |
8980 KB |
Output is correct |
| 19 |
Correct |
2031 ms |
8932 KB |
Output is correct |
| 20 |
Correct |
1991 ms |
8892 KB |
Output is correct |
| 21 |
Correct |
1983 ms |
8860 KB |
Output is correct |
| 22 |
Correct |
1992 ms |
8840 KB |
Output is correct |
| 23 |
Correct |
1962 ms |
8928 KB |
Output is correct |
| 24 |
Correct |
1954 ms |
8920 KB |
Output is correct |
| 25 |
Correct |
2065 ms |
8804 KB |
Output is correct |
