oj.uz

Submission #224127

# Submission time Handle Problem Language Result Execution time Memory
224127 2020-04-17T08:33:28 Z shenxy Fire (JOI20_ho_t5) C++11
14 / 100
 1000 ms 43256 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]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 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 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 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 5 ms 384 KB Output is correct
11 Correct 5 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
16 Correct 5 ms 256 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 5 ms 256 KB Output is correct
20 Correct 5 ms 256 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 256 KB Output is correct
23 Correct 5 ms 256 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 256 KB Output is correct
26 Correct 5 ms 256 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 256 KB Output is correct
31 Correct 5 ms 256 KB Output is correct
32 Correct 5 ms 256 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 206 ms 28300 KB Output is correct
3 Correct 206 ms 28392 KB Output is correct
4 Correct 214 ms 28648 KB Output is correct
5 Correct 228 ms 28908 KB Output is correct
6 Correct 206 ms 28656 KB Output is correct
7 Correct 216 ms 28904 KB Output is correct
8 Correct 239 ms 29164 KB Output is correct
9 Correct 211 ms 29032 KB Output is correct
10 Correct 210 ms 28396 KB Output is correct
11 Correct 204 ms 29040 KB Output is correct
12 Correct 202 ms 28396 KB Output is correct
13 Correct 215 ms 28904 KB Output is correct
14 Correct 211 ms 28816 KB Output is correct
15 Correct 212 ms 28904 KB Output is correct
16 Correct 209 ms 28652 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 421 ms 42392 KB Output is correct
3 Correct 408 ms 42096 KB Output is correct
4 Correct 440 ms 43256 KB Output is correct
5 Correct 405 ms 42112 KB Output is correct
6 Correct 410 ms 42620 KB Output is correct
7 Correct 414 ms 42616 KB Output is correct
8 Correct 524 ms 42744 KB Output is correct
9 Correct 414 ms 42104 KB Output is correct
10 Correct 444 ms 41836 KB Output is correct
11 Correct 417 ms 43128 KB Output is correct
12 Correct 518 ms 42616 KB Output is correct
13 Correct 493 ms 43128 KB Output is correct
14 Correct 406 ms 42232 KB Output is correct
15 Correct 405 ms 43000 KB Output is correct
16 Correct 503 ms 42584 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 35448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 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 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 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 5 ms 384 KB Output is correct
11 Correct 5 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
16 Correct 5 ms 256 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 5 ms 256 KB Output is correct
20 Correct 5 ms 256 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 256 KB Output is correct
23 Correct 5 ms 256 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 256 KB Output is correct
26 Correct 5 ms 256 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 256 KB Output is correct
31 Correct 5 ms 256 KB Output is correct
32 Correct 5 ms 256 KB Output is correct
33 Execution timed out 1096 ms 38164 KB Time limit exceeded
34 Halted 0 ms 0 KB -