oj.uz

Submission #70893

# Submission time Handle Problem Language Result Execution time Memory
70893 2018-08-23T16:01:01 Z AlphaRazra Worst Reporter 3 (JOI18_worst_reporter3) C++14
19 / 100
 1189 ms 263168 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(){
	ios::sync_with_stdio(0); cin.tie(0);
	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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1062 ms 15696 KB Output is correct
2 Correct 1107 ms 31112 KB Output is correct
3 Correct 1151 ms 46736 KB Output is correct
4 Correct 1162 ms 62164 KB Output is correct
5 Correct 1189 ms 77816 KB Output is correct
6 Correct 1155 ms 93292 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1062 ms 15696 KB Output is correct
2 Correct 1107 ms 31112 KB Output is correct
3 Correct 1151 ms 46736 KB Output is correct
4 Correct 1162 ms 62164 KB Output is correct
5 Correct 1189 ms 77816 KB Output is correct
6 Correct 1155 ms 93292 KB Output is correct
7 Correct 4 ms 93292 KB Output is correct
8 Correct 4 ms 93292 KB Output is correct
9 Correct 3 ms 93292 KB Output is correct
10 Correct 3 ms 93292 KB Output is correct
11 Correct 4 ms 93292 KB Output is correct
12 Correct 3 ms 93292 KB Output is correct
13 Correct 681 ms 107416 KB Output is correct
14 Correct 590 ms 123880 KB Output is correct
15 Correct 563 ms 139096 KB Output is correct
16 Correct 695 ms 154960 KB Output is correct
17 Correct 807 ms 174988 KB Output is correct
18 Correct 900 ms 193548 KB Output is correct
19 Correct 797 ms 211828 KB Output is correct
20 Correct 789 ms 230100 KB Output is correct
21 Correct 869 ms 247636 KB Output is correct
22 Runtime error 793 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
23 Halted 0 ms 0 KB -