oj.uz

답안 #224123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
224123 2020-04-17T08:30:59 Z shenxy Fire (JOI20_ho_t5) C++11
0 / 100
 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]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 256 KB Output isn't correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 256 KB Output isn't correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 256 KB Output isn't correct

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1089 ms 35704 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 256 KB Output isn't correct