oj.uz

Submission #110308

# Submission time Handle Problem Language Result Execution time Memory
110308 2019-05-10T16:25:04 Z ryansee Worst Reporter 3 (JOI18_worst_reporter3) C++14
100 / 100
 1396 ms 29472 KB 
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)*2
#define MAXK 26
#define MAXX 15000006
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph emplace
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n, q, A[MAXN], mi[MAXN]; // mi - stands for mini place IOI-chan has to be, in order for him to move up
int main()
{
	FAST
	cin>>n>>q;
	FOR(i,1,n+1)cin>>A[i];
	mi[0]=1;
	FOR(i,1,n+1) { // now we calculate mi[i]; - based on mi[i-1];
		mi[i] = (((A[i] - 1)/mi[i-1]+1)*mi[i-1]); if(0)cerr<<mi[i]<<'\n';
	}
	FOR(i,0,q) {
		ll t,l,r;cin>>t>>l>>r;
		ll st = 0, en = n+1, mid = 0;
		while(en-st>1) {
			mid=(st+en)>>1ll;
			if(t/mi[mid]*mi[mid]-mid >= l) st=mid;
			else en=mid;
		}
		ll ans1 = st;
		st=0,en=n+1,mid=0;
		while(en-st>1) {
			mid=(st+en)>>1ll;
			if(t/mi[mid]*mi[mid]-mid>r)st=mid;
			else en=mid;
		}
		ll ans2=st;
				// cerr << ans1 << " " << ans2 << ' ' << t << ' ' << mi[1] << ' ';
		cout<<ans1-ans2+(l<=t&&t<=r)<<'\n';
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1176 ms 26044 KB Output is correct
2 Correct 1367 ms 26844 KB Output is correct
3 Correct 1289 ms 26664 KB Output is correct
4 Correct 1149 ms 26752 KB Output is correct
5 Correct 1098 ms 26872 KB Output is correct
6 Correct 1396 ms 26692 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1176 ms 26044 KB Output is correct
2 Correct 1367 ms 26844 KB Output is correct
3 Correct 1289 ms 26664 KB Output is correct
4 Correct 1149 ms 26752 KB Output is correct
5 Correct 1098 ms 26872 KB Output is correct
6 Correct 1396 ms 26692 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 637 ms 25320 KB Output is correct
14 Correct 703 ms 25848 KB Output is correct
15 Correct 693 ms 24380 KB Output is correct
16 Correct 728 ms 25008 KB Output is correct
17 Correct 911 ms 29252 KB Output is correct
18 Correct 873 ms 29420 KB Output is correct
19 Correct 812 ms 29380 KB Output is correct
20 Correct 907 ms 29272 KB Output is correct
21 Correct 849 ms 29244 KB Output is correct
22 Correct 845 ms 29472 KB Output is correct
23 Correct 959 ms 29240 KB Output is correct
24 Correct 904 ms 29256 KB Output is correct
25 Correct 1213 ms 26848 KB Output is correct
26 Correct 1061 ms 26684 KB Output is correct
27 Correct 910 ms 29032 KB Output is correct
28 Correct 936 ms 29284 KB Output is correct
29 Correct 911 ms 28792 KB Output is correct
30 Correct 863 ms 28920 KB Output is correct
31 Correct 888 ms 29068 KB Output is correct
32 Correct 810 ms 25288 KB Output is correct
33 Correct 3 ms 512 KB Output is correct