oj.uz

Submission #201462

# Submission time Handle Problem Language Result Execution time Memory
201462 2020-02-10T16:03:32 Z extraterrestrial Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 940 ms 33396 KB 
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll

const int N = 5e5 + 10;
int a[N];
pair<int, int> par[N];

inline int get(int id, int t) {
	return -id + (t / par[id].F) * par[id].S;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, q;;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
  	cin >> a[i];
  }
  par[0] = {1, 1};
  for (int i = 1; i <= n; i++) {
  	int cnt = (a[i] + par[i - 1].S - 1) / par[i - 1].S;
  	par[i] = {par[i - 1].F * cnt, par[i - 1].S * cnt};
  	//cout << par[i].F << ' ' << par[i].S << '\n';
  }
  for (int i = 0; i < q; i++) {
  	int l, r, t;
  	cin >> t >> l >> r;
  	if (get(0, t) < l || get(n, t) > r) {
  		cout << 0 << '\n';
  		continue;
  	}
  	int lo1 = 0, hi1 = n + 1;
  	while (hi1 - lo1 > 1) {
  		int mid = (lo1 + hi1) / 2;
  		if (get(mid, t) >= l) {
  			lo1 = mid;
  		}
  		else {
  			hi1 = mid;
  		}
  	}
  	int lo2 = -1, hi2 = n;
  	while (hi2 - lo2 > 1) {
  		int mid = (lo2 + hi2) / 2;
  		if (get(mid, t) <= r) {
  			hi2 = mid;
  		}
  		else {
  			lo2 = mid;
  		}
  	}
  	//cout << lo1 << ' ' << hi2 << '\n';
  	cout << lo1 - hi2 + 1 << '\n';
  }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 30584 KB Output is correct
2 Correct 940 ms 30584 KB Output is correct
3 Correct 934 ms 30584 KB Output is correct
4 Correct 938 ms 30712 KB Output is correct
5 Correct 913 ms 30584 KB Output is correct
6 Correct 879 ms 30724 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 30584 KB Output is correct
2 Correct 940 ms 30584 KB Output is correct
3 Correct 934 ms 30584 KB Output is correct
4 Correct 938 ms 30712 KB Output is correct
5 Correct 913 ms 30584 KB Output is correct
6 Correct 879 ms 30724 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 486 ms 28988 KB Output is correct
14 Correct 501 ms 29816 KB Output is correct
15 Correct 490 ms 28452 KB Output is correct
16 Correct 493 ms 28900 KB Output is correct
17 Correct 614 ms 33148 KB Output is correct
18 Correct 609 ms 33396 KB Output is correct
19 Correct 607 ms 33144 KB Output is correct
20 Correct 613 ms 33144 KB Output is correct
21 Correct 621 ms 33168 KB Output is correct
22 Correct 582 ms 33148 KB Output is correct
23 Correct 622 ms 33144 KB Output is correct
24 Correct 608 ms 33272 KB Output is correct
25 Correct 932 ms 30584 KB Output is correct
26 Correct 912 ms 30712 KB Output is correct
27 Correct 679 ms 32760 KB Output is correct
28 Correct 662 ms 33108 KB Output is correct
29 Correct 636 ms 32504 KB Output is correct
30 Correct 667 ms 32680 KB Output is correct
31 Correct 659 ms 32944 KB Output is correct
32 Correct 639 ms 29176 KB Output is correct
33 Correct 5 ms 376 KB Output is correct