Submission #46597

#	Time	Username	Problem	Language	Result	Execution time	Memory
46597		Bruteforceman	Worst Reporter 3 (JOI18_worst_reporter3)	C++11	100 / 100	1266 ms	262144 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
int n;
int a[500010];
long long dp[500010];
const long long inf = 1000000000 + 7;
int Time;

int get_time(int T, int idx) {
	return ((T / dp[idx]) * dp[idx]) - idx; 
}
int left_point (int b, int e, int val) {
	if(b == e) {
		return get_time(Time, b) >= val ? b : -1;
	}
	int m = (b + e + 1) >> 1;
	if(get_time(Time, m) >= val) return left_point (m, e, val);
	else return left_point (b, m-1, val);
} 
int right_point (int b, int e, int val) {
	if(b == e) {
		return get_time(Time, b) <= val ? b : -1; 
	}
	int m = (b + e) >> 1;
	if(get_time(Time, m) <= val) return right_point(b, m, val);
	else return right_point(m + 1, e, val);
}
int query(int t, int l, int r) {
	Time = t;
	int add = 0;
	int x = left_point(1, n, l);
	int y = right_point(1, n, r);
	if(l <= t && t <= r) add = 1;
	if(x == -1 || y == -1) return add; 
	return add + (x - y + 1);
}

int main() {
	int q;
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	dp[1] = a[1];
	for(int i = 1; i < n; i++) {
		dp[i + 1] = (((a[i + 1] - 1) / dp[i]) + 1) * dp[i];
		dp[i + 1] = min(inf, dp[i + 1]);
	}	

	while(q--) {
		int t, l, r;
		scanf("%d %d %d", &t, &l, &r);
		printf("%d\n", query(t, l, r));
	}
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:40: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:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:52: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