Submission #242214

#	Time	Username	Problem	Language	Result	Execution time	Memory
242214		shenxy	Worst Reporter 3 (JOI18_worst_reporter3)	C++11	100 / 100	1521 ms	17372 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 Fenwick {
	vector<int> ft;
	Fenwick(int N) {
		for (int i = 0; i <= N; ++i) ft.push_back(0);
	}
	void update(int i, int dv) {
		for (; i <= ft.size(); i += i & -i) ft[i] += dv;
	}
};
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)));
	Fenwick f(1 << 19);
	for (int i = 2; i <= N + 1; ++i) f.update(i, -1);
	T = 0;
	for (q i: queries) {
		for (jmp j: jumps) f.update(j.S.F + 1, j.F * (i.F.F / j.F - T / j.F)), f.update(j.S.S + 2, -j.F * (i.F.F / j.F - T / j.F));
		int l = 1, r = 1 << 19, m, v = 0, a1;
		while (l != r) {
			m = (l + r) >> 1;
			if (v + f.ft[m] >= i.S.F) l = m + 1, v += f.ft[m];
			else r = m;
		}
		a1 = l;
		l = 1, r = 1 << 19, v = 0;
		while (l != r) {
			m = (l + r) >> 1;
			if (v + f.ft[m] > i.S.S) l = m + 1, v += f.ft[m];
			else r = m;
		}
		ans[i.F.S] = a1 - l;
		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 member function 'void Fenwick::update(int, int)':
worst_reporter3.cpp:16:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; i <= ft.size(); i += i & -i) ft[i] += dv;
          ~~^~~~~~~~~~~~
worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:21: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:24: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:26: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: 81 / 81