oj.uz

Submission #197823

# Submission time Handle Problem Language Result Execution time Memory
197823 2020-01-23T14:00:42 Z gs18081 Worst Reporter 3 (JOI18_worst_reporter3) C++11
100 / 100
 515 ms 25564 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 381 ms 22884 KB Output is correct
2 Correct 374 ms 22604 KB Output is correct
3 Correct 375 ms 22884 KB Output is correct
4 Correct 372 ms 22776 KB Output is correct
5 Correct 376 ms 22848 KB Output is correct
6 Correct 372 ms 22904 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 22884 KB Output is correct
2 Correct 374 ms 22604 KB Output is correct
3 Correct 375 ms 22884 KB Output is correct
4 Correct 372 ms 22776 KB Output is correct
5 Correct 376 ms 22848 KB Output is correct
6 Correct 372 ms 22904 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 404 KB Output is correct
13 Correct 391 ms 21436 KB Output is correct
14 Correct 396 ms 21880 KB Output is correct
15 Correct 373 ms 20600 KB Output is correct
16 Correct 388 ms 21240 KB Output is correct
17 Correct 479 ms 25464 KB Output is correct
18 Correct 475 ms 25336 KB Output is correct
19 Correct 515 ms 25564 KB Output is correct
20 Correct 478 ms 25564 KB Output is correct
21 Correct 474 ms 25292 KB Output is correct
22 Correct 474 ms 25312 KB Output is correct
23 Correct 482 ms 25376 KB Output is correct
24 Correct 477 ms 25456 KB Output is correct
25 Correct 381 ms 22764 KB Output is correct
26 Correct 384 ms 22928 KB Output is correct
27 Correct 484 ms 25152 KB Output is correct
28 Correct 491 ms 25340 KB Output is correct
29 Correct 494 ms 24800 KB Output is correct
30 Correct 501 ms 25072 KB Output is correct
31 Correct 494 ms 25112 KB Output is correct
32 Correct 361 ms 21496 KB Output is correct
33 Correct 2 ms 376 KB Output is correct