This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;
const int SZ = 1 << 17, SQ = 8;
ll X[SZ], ans[SZ], S[SZ];
struct Query {
int s, e, id;
Query(int a = 0, int b = 0, int c = 0) {
s = a, e = b, id = c;
}
const bool operator<(Query& a) {
if ((s >> SQ) != (a.s >> SQ)) return (s >> SQ) < (a.s >> SQ);
return e > a.e;
}
} QS[SZ];
struct Seg {
ll T[SZ << 1];
void Update(int i, ll v) {
T[i += SZ - 1] += v;
while (i >>= 1) T[i] = max(T[i * 2], T[i * 2 + 1]);
}
} T;
void Add(int idx) {
T.Update(S[idx], X[idx]);
}
void Sub(int idx) {
T.Update(S[idx], -X[idx]);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N, Q;
cin >> N >> Q;
map<int, int> occur;
for (int i = 1; i <= N; ++i) {
cin >> X[i];
if (occur.find(X[i]) == occur.end()) S[i] = occur[X[i]] = i;
else S[i] = occur[X[i]];
}
for (int i = 0; i < Q; ++i) {
int s, e;
cin >> s >> e;
QS[i] = Query(s, e, i);
}
sort(QS, QS + Q);
int L = 1, R = 0;
for (int d = 0; d < Q; ++d) {
auto [s, e, id] = QS[d];
while (R < e) Add(++R);
while (s < L) Add(--L);
while (e < R) Sub(R--);
while (L < s) Sub(L++);
ans[id] = T.T[1];
}
for (int i = 0; i < Q; ++i) cout << ans[i] << '\n';
return 0;
}
# | 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... |