Submission #242210

#	Time	Username	Problem	Language	Result	Execution time	Memory
242210		shenxy	Worst Reporter 3 (JOI18_worst_reporter3)	C++11	19 / 100	2091 ms	62072 KiB

worst_reporter3

#include <cstdio>
#include <algorithm>
#include <vector>
#define F first
#define S second
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> jmp;
typedef pair<ii, ii> q;
struct seg {
	int s, e, m, minv, lazy;
	seg *l, *r;
	seg(int _s, int _e) {
		s = _s, e = _e, m = (s + e) / 2, minv = -e, lazy = 0;
		if (s != e) {
			l = new seg(s, m);
			r = new seg(m + 1, e);
		}
	}
	void prop() {
		if (lazy != 0) {
			minv += lazy;
			if (s != e) {
				l -> lazy += lazy;
				r -> lazy += lazy;
			}
			lazy = 0;
		}
	}
	void update(int a, int b, int dv) {
		if (s != a || e != b) {
			if (a > m) r -> update(a, b, dv);
			else if (b <= m) l -> update(a, b, dv);
			else l -> update(a, m, dv), r -> update(m + 1, b, dv);
			l -> prop(), r -> prop();
			minv = min(l -> minv, r -> minv);
		} else lazy += dv;
	}
	int lidx(int i) {
		if (s != e) {
			l -> prop(), r -> prop();
			if (l -> minv <= i) return l -> lidx(i);
			else if (r -> minv <= i) return r -> lidx(i);
			else return e + 1;
		} else return s;
	}
} *root;
int main() {
	int N, Q;
	scanf("%d %d", &N, &Q);
	int D[N], T, L, R, ans[Q];
	q queries[Q];
	for (int i = 0; i < N; ++i) scanf("%d", &D[i]);
	for (int i = 0; i < Q; ++i) {
		scanf("%d %d %d", &T, &L, &R);
		queries[i] = q(ii(T, i), ii(L, R));
	}
	sort(queries, queries + Q);
	vector<jmp> jumps;
	int j = 1, l = 0;
	for (int i = 0; i < N; ++i) {
		if (D[i] > j) {
			jumps.push_back(jmp(j, ii(l, i)));
			j = j * ((D[i] + j - 1) / j);
			l = i + 1;
		}
	}
	jumps.push_back(jmp(j, ii(l, N)));
	root = new seg(0, N);
	T = 0;
	for (q i: queries) {
		for (jmp j: jumps) root -> update(j.S.F, j.S.S, j.F * (i.F.F / j.F - T / j.F));
		root -> prop();
		ans[i.F.S] = root -> lidx(i.S.F - 1) - root -> lidx(i.S.S);
		T = i.F.F;
	}
	for (int i = 0; i < Q; ++i) printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
worst_reporter3.cpp:53: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("%d", &D[i]);
                              ~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &T, &L, &R);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 81