oj.uz

Submission #70892

# Submission time Handle Problem Language Result Execution time Memory
70892 2018-08-23T16:00:05 Z AlphaRazra Worst Reporter 3 (JOI18_worst_reporter3) C++14
12 / 100
 2000 ms 21624 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define fs first
#define sc second
#define pb push_back
#define debug(x) cout<<#x<<" = "<<(x)<<endl
#define mod 998244353
#define INF 1e18
using namespace std;

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

int n,q;
long long a[500005];
long long mov[500005];
long long t,l,r;

bool cek(long long dist,int idx){
	long long nyak = t / mov[idx];
	nyak = nyak * mov[idx];

	nyak = nyak - idx;
	if(nyak <= dist){
		return true;
	}
	return false;
}

int main(){
	cin >> n >> q;

	mov[0] = 1;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		long long nyak = a[i] / mov[i - 1];
		if(a[i] % mov[i - 1] != 0){
			nyak++;
		}
		mov[i] = mov[i - 1] * nyak;
	//	cout << i << " " << mov[i] << " here\n";
	}

	for(int i = 1; i <= q; i++){
		cin >> t >> l >> r;
		int kiri,kanan,ansL,ansR;

		l--;
		kiri = 1, kanan = n;
		ansL = n + 1;
		while(kiri <= kanan){
			int mid = (kiri + kanan) / 2;

			if(cek(l,mid)){
				ansL = mid;
				kanan = mid - 1;
			}else{
				kiri = mid + 1;
			}
		}
		kiri = 1; kanan = n;
		ansR = n + 1;
		while(kiri <= kanan){
			int mid = (kiri + kanan) / 2;

			if(cek(r,mid)){
				ansR = mid;
				kanan = mid - 1;
			}else{
				kiri = mid + 1;
			}
		}
		int tamb = 0;
		if(t > l && t <= r) tamb = 1;
		cout << ansL - ansR + tamb << "\n";
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 21624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 21624 KB Time limit exceeded
2 Halted 0 ms 0 KB -