| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 224123 |
2020-04-17T08:30:59 Z |
shenxy |
Fire (JOI20_ho_t5) |
C++11 |
|
1000 ms |
35704 KB |
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
struct seg {
int s, e, m, v;
seg *l, *r;
seg(int _s, int _e) {
s = _s, e = _e, m = (s + e) / 2, v = 0;
if (s != e) {
l = new seg(s, m);
r = new seg(m + 1, e);
}
}
void update(int i, int nv) {
if (s != e) {
if (i > m) r -> update(i, nv);
else l -> update(i, nv);
v = max(l -> v, r -> v);
} else v = nv;
}
int query(int a, int b) {
if (s == a && e == b) return v;
if (a > m) return r -> query(a, b);
if (b <= m) return l -> query(a, b);
return max(l -> query(a, m), r -> query(m + 1, b));
}
} *root;
int main() {
int N, Q;
scanf("%d %d", &N, &Q);
long long S[N];
int T[Q], L[Q], R[Q];
for (int i = 0; i < N; ++i) scanf("%lld", &S[i]);
map<int, vector<int> > queries;
for (int i = 0; i < Q; ++i) scanf("%d %d %d", &T[i], &L[i], &R[i]);
for (int i = 0; i < Q; ++i) queries[T[i]].push_back(i);
if (queries.size() == 1) {
root = new seg(0, N - 1);
for (int i = 0; i < N; ++i) root -> update(i, S[i]);
for (int i = 0; i < N; ++i) S[i] = root -> query(max(0, i - queries.begin() -> first), i);
for (int i = 1; i < N; ++i) S[i] += S[i - 1];
for (int i = 0; i < Q; ++i) printf("%lld\n", S[R[i] - 1] - L[i] == 1 ? 0 : S[L[i] - 2]);
return 0;
}/* else if (*max_element(S, S + N) <= 2) {
} */else {
root = new seg(0, N - 1);
for (int i = 0; i < N; ++i) root -> update(i, S[i]);
for (int i = 0; i < Q; ++i) {
long long ans = 0;
for (int j = L[i] - 1; j < R[i]; ++j) ans += root -> query(max(0, j - T[i]), j);
printf("%lld\n", ans);
}
}
}
Compilation message
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp:35:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < N; ++i) scanf("%lld", &S[i]);
~~~~~^~~~~~~~~~~~~~~
ho_t5.cpp:37:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < Q; ++i) scanf("%d %d %d", &T[i], &L[i], &R[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
35704 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
