oj.uz

Submission #46597

# Submission time Handle Problem Language Result Execution time Memory
46597 2018-04-22T06:46:58 Z Bruteforceman Worst Reporter 3 (JOI18_worst_reporter3) C++11
100 / 100
 1266 ms 262144 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1055 ms 24668 KB Output is correct
2 Correct 1266 ms 40296 KB Output is correct
3 Correct 1125 ms 56024 KB Output is correct
4 Correct 1164 ms 71464 KB Output is correct
5 Correct 1126 ms 86868 KB Output is correct
6 Correct 1075 ms 102272 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 102272 KB Output is correct
2 Correct 3 ms 102272 KB Output is correct
3 Correct 3 ms 102272 KB Output is correct
4 Correct 3 ms 102272 KB Output is correct
5 Correct 3 ms 102272 KB Output is correct
6 Correct 3 ms 102272 KB Output is correct

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1055 ms 24668 KB Output is correct
2 Correct 1266 ms 40296 KB Output is correct
3 Correct 1125 ms 56024 KB Output is correct
4 Correct 1164 ms 71464 KB Output is correct
5 Correct 1126 ms 86868 KB Output is correct
6 Correct 1075 ms 102272 KB Output is correct
7 Correct 3 ms 102272 KB Output is correct
8 Correct 3 ms 102272 KB Output is correct
9 Correct 3 ms 102272 KB Output is correct
10 Correct 3 ms 102272 KB Output is correct
11 Correct 3 ms 102272 KB Output is correct
12 Correct 3 ms 102272 KB Output is correct
13 Correct 694 ms 116488 KB Output is correct
14 Correct 735 ms 133116 KB Output is correct
15 Correct 687 ms 148420 KB Output is correct
16 Correct 700 ms 164252 KB Output is correct
17 Correct 876 ms 184284 KB Output is correct
18 Correct 841 ms 202804 KB Output is correct
19 Correct 859 ms 221496 KB Output is correct
20 Correct 889 ms 239960 KB Output is correct
21 Correct 855 ms 258648 KB Output is correct
22 Correct 876 ms 262144 KB Output is correct
23 Correct 863 ms 262144 KB Output is correct
24 Correct 847 ms 262144 KB Output is correct
25 Correct 1044 ms 262144 KB Output is correct
26 Correct 1112 ms 262144 KB Output is correct
27 Correct 892 ms 262144 KB Output is correct
28 Correct 869 ms 262144 KB Output is correct
29 Correct 889 ms 262144 KB Output is correct
30 Correct 913 ms 262144 KB Output is correct
31 Correct 909 ms 262144 KB Output is correct
32 Correct 839 ms 262144 KB Output is correct
33 Correct 2 ms 262144 KB Output is correct