Submission #220210

#	Time	Username	Problem	Language	Result	Execution time	Memory
220210		patrikpavic2	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	582 ms	25648 KiB

worst_reporter3

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 5e5  + 500;

ll D[N];
int n, q, nxt[N];

int kolko(ll T,ll L,ll R){
	ll tren = T;
	int ans = 0;
	for(int i = 0;i <= n;i = nxt[i]){
		ll R2 = tren * D[i] - i, L2 = tren * D[i] - nxt[i] + 1;
		if(max(L, L2) <= min(R, R2))
			ans += min(R, R2) - max(L, L2) + 1;
		if(nxt[i] <= n)
			tren = tren / (D[nxt[i]] / D[i]);
		if(!tren) 
			break;
	}
	return ans;
}

int main(){
	scanf("%d%d", &n, &q);
	D[0] = 1;
	for(int i = 1;i <= n;i++){
		scanf("%lld", D + i);
		if(D[i] < D[i - 1])
			D[i] = D[i - 1];
		else if(D[i] % D[i - 1])
			D[i] += D[i - 1] - D[i] % D[i - 1];
	}
	int lst = 0;
	for(int i = 1;i <= n;i++){
		if(D[i] != D[lst]){
			nxt[lst] = i;
			lst = i;
		}
	}
	nxt[lst] = n + 1;
	for(;q--;){
		ll A, B, C; scanf("%lld%lld%lld", &A, &B, &C);
		printf("%d\n", kolko(A, B, C));
	}
	return 0;
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:35: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:38: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:53:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll A, B, C; scanf("%lld%lld%lld", &A, &B, &C);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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