Submission #224143

#	Time	Username	Problem	Language	Result	Execution time	Memory
224143		shenxy	Fire (JOI20_ho_t5)	C++11	20 / 100	1084 ms	44920 KiB

ho_t5

#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, ii> query;
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;
struct Fenwick {
	int s;
	vector<long long> f;
	Fenwick(int N) {
		s = N;
		f = vector<long long>(s + 1, 0);
	}
	void update(int i, long long v) {
		for (; i <= s; i += i & -i) f[i] += v;
	}
	long long query(int a) {
		long long ans = 0;
		for (; a > 0; a -= a & -a) ans += f[a];
		return ans;
	}
};
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]));
	} else if (*max_element(S, S + N) <= 2) {
		int prev1 = -1, prev2 = -1;
		set<query> q;
		Fenwick f(N);
		for (int i = 0; i < N; ++i) f.update(i + 1, S[i]);
		long long ans[Q];
		for (int i = 0; i < N; ++i) {
			if (S[i] == 0) {
				if (prev2 != -1) q.insert(query(ii(i - prev2, -1), ii(2, i + 1)));
				else if (prev1 != -1) q.insert(query(ii(i - prev1, -1), ii(1, i + 1)));
			} else if (S[i] == 1) {
				if (prev2 != -1) q.insert(query(ii(i - prev2, -1), ii(1, i + 1)));
				prev1 = i;
			} else prev2 = i;
		}
		for (int i = 0; i < Q; ++i) q.insert(query(ii(T[i], i), ii(L[i], R[i])));
		for (query i: q) {
			if (i.first.second == -1) f.update(i.second.second, i.second.first);
			else ans[i.first.second] = f.query(i.second.second) - f.query(i.second.first - 1);
		}
		for (int i = 0; i < Q; ++i) printf("%lld\n", ans[i]);
	} 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);
		}
	}
	return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:51: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:54: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:56: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 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 0 / 80