Submission #296789

#	Time	Username	Problem	Language	Result	Execution time	Memory
296789		Plurm	Worst Reporter 3 (JOI18_worst_reporter3)	C++11	100 / 100	521 ms	27544 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
int d[500005]; // Period
long long p[500005]; // Period
const long long INF = 1e18+7ll;
vector<int> pivots;
long long intersectSegment(long long l1, long long r1, long long l2, long long r2){
	auto l = max(l1, l2);
	auto r = min(r1, r2);
	if(l > r) return 0ll;
	else return r - l + 1;
}
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i = 1; i <= n; i++){
		scanf("%d",d+i);
		if(i == 1) p[i] = d[i];
		else if(p[i-1] == INF) p[i] = INF;
		else p[i] = 1ll * (d[i] + p[i-1] - 1ll) / p[i-1] * p[i-1];
		if(p[i] > INF) p[i] = INF;
	}
	for(int i = 1; i <= n; i++){
		if(p[i] != p[i-1]) pivots.push_back(i);
	}
	// Assume |pivots| < 32 (provable but this margin is too small to contain)
	for(int i = 0; i < q; i++){
		int t, l, r;
		scanf("%d%d%d",&t,&l,&r);
		int ans = l <= t && t <= r ? 1 : 0;
		for(int j = 0; j < pivots.size(); j++){
			int cpv = pivots[j];
			int npv = j == pivots.size()-1 ? n : pivots[j+1]-1;
			long long bckt = 1ll * t / p[cpv] * p[cpv];
			ans += intersectSegment(bckt-r, bckt-l, cpv, npv);
		}
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int j = 0; j < pivots.size(); j++){
      |                  ~~^~~~~~~~~~~~~~~
worst_reporter3.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    int npv = j == pivots.size()-1 ? n : pivots[j+1]-1;
      |              ~~^~~~~~~~~~~~~~~~~~
worst_reporter3.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
worst_reporter3.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |   scanf("%d",d+i);
      |   ~~~~~^~~~~~~~~~
worst_reporter3.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |   scanf("%d%d%d",&t,&l,&r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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