Submission #197823

#	Time	Username	Problem	Language	Result	Execution time	Memory
197823		gs18081	Worst Reporter 3 (JOI18_worst_reporter3)	C++11	100 / 100	515 ms	25564 KiB

worst_reporter3

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 505050;

int v[MAXN];
int cnt = 0;
int N,Q;
int arr[MAXN];
int s[MAXN];
int e[MAXN];



int main(){
	scanf("%d %d",&N,&Q);
	v[0] = 1;
	cnt = 1;
	for(int i=1;i<=N;i++){
		scanf("%d",arr+i);
		if(arr[i] <= v[i-1]){
			v[i] = v[i-1];
			e[cnt] = i;
		}
		else{
			v[i] = v[i-1] * (1 + ( (arr[i] - 1) / v[i-1]));
			cnt++;
			s[cnt] = e[cnt] = i;
		}
	}
	for(int i=1;i<=cnt;i++){
		//printf("%d %d %d\n",s[i],e[i],v[s[i]]);
	}
	for(int i=0;i<Q;i++){
		int a,b,c;
		scanf("%d %d %d",&c,&a,&b);
		int ans = 0;
		//printf("%d\n",i);
		for(int j=1;j<=cnt;j++){
			int d = v[s[j]] * (c / v[s[j]]);
			int ts = d - e[j];
			int te = d - s[j];
		//	printf("%d %d %d\n",j,ts,te);
			if(te < a) continue;
			if(b < ts) continue;
			int tte = min(te , b);
			int tts = max(a , ts);
			ans += tte - tts + 1;
		}
		printf("%d\n",ans);
	}
	return 0;
}

Compilation message (stderr)

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

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