oj.uz

Submission #553468

# Submission time Handle Problem Language Result Execution time Memory
553468 2022-04-25T23:49:00 Z MohamedAhmed04 Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 505 ms 20740 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5e5 + 10 ;

int arr[MAX] ;
int n , q ;

bool check(int idx , int x , int t)
{
	return (-idx + t / arr[idx] * arr[idx] <= x) ;
}

int calc(int x , int t)
{
	int l = 0 , r = n ;
	int ans = n+1 ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(check(mid , x , t))
			ans = mid , r = mid-1 ;
		else
			l = mid+1 ;
	}
	return (n-ans+1) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>q ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	arr[0] = 1 ;
	for(int i = 1 ; i <= n ; ++i)
		arr[i] = (arr[i] + arr[i-1] - 1) / arr[i-1] * arr[i-1] ;
	while(q--)
	{
		int t , l , r ;
		cin>>t>>l>>r ;
		cout<<calc(r , t) - calc(l-1 , t)<<"\n" ;
	}
	return 0 ;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 20712 KB Output is correct
2 Correct 498 ms 20720 KB Output is correct
3 Correct 491 ms 20740 KB Output is correct
4 Correct 488 ms 20640 KB Output is correct
5 Correct 486 ms 20688 KB Output is correct
6 Correct 505 ms 20664 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 20712 KB Output is correct
2 Correct 498 ms 20720 KB Output is correct
3 Correct 491 ms 20740 KB Output is correct
4 Correct 488 ms 20640 KB Output is correct
5 Correct 486 ms 20688 KB Output is correct
6 Correct 505 ms 20664 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Runtime error 52 ms 9420 KB Execution killed with signal 8
14 Halted 0 ms 0 KB -