Submission #100557

#	Time	Username	Problem	Language	Result	Execution time	Memory
100557		JPN20	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	712 ms	13176 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;

long long N, Q, D[1 << 19];
vector<tuple<int, int, long long>>tup;

long long solve(long long T, long long L, long long R) {
	long long sum = 0;
	for (int i = 0; i < tup.size(); i++) {
		long long E = (T / get<2>(tup[i])) * get<2>(tup[i]);
		long long EL = -1LL * get<1>(tup[i]) + E;
		long long ER = -1LL * get<0>(tup[i]) + E;
		long long PL = max(EL, L), PR = min(ER, R);
		if (PL <= PR) sum += (PR - PL + 1);
	}
	if (L <= T && T <= R) sum++;
	return sum;
}

int main() {
	scanf("%lld%lld", &N, &Q);
	for (int i = 1; i <= N; i++) {
		scanf("%lld", &D[i]);
		if (i >= 2) { D[i] += D[i - 1] - 1; D[i] /= D[i - 1]; D[i] *= D[i - 1]; }
	}
	int t = 1;
	for (int i = 1; i <= N; i++) {
		if (i == N || D[i] != D[i + 1]) {
			tup.push_back(make_tuple(t, i, D[i]));
			t = i + 1;
		}
	}
	for (int i = 1; i <= Q; i++) {
		long long T, L, R;
		scanf("%lld%lld%lld", &T, &L, &R);
		printf("%lld\n", solve(T, L, R));
	}
	return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'long long int solve(long long int, long long int, long long int)':
worst_reporter3.cpp:9:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < tup.size(); i++) {
                  ~~^~~~~~~~~~~~
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("%lld%lld", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
worst_reporter3.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &D[i]);
   ~~~~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &T, &L, &R);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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