oj.uz

Submission #216067

# Submission time Handle Problem Language Result Execution time Memory
216067 2020-03-26T17:10:41 Z someone_aa Worst Reporter 3 (JOI18_worst_reporter3) C++17
0 / 100
 2000 ms 24484 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 500100;
ll d[maxn], n, q;
ll blocksize[maxn];

ll f(int i, int t) {
	return (-i) + (t/blocksize[i]) * blocksize[i];
}

int main() {
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin>>d[i];
	}

	blocksize[0] = 1;
	blocksize[1] = d[1];
	for(int i=2;i<=n;i++) {
		blocksize[i] = blocksize[i-1] * int((d[i]+blocksize[i-1]-1)/(blocksize[i-1]));
		//cout<<i<<": "<<blocksize[i]<<" = "<<blocksize[i-1]<<" * "<<(d[i]+blocksize[i-1]-1)/(blocksize[i-1])<<"\n";
	}

	int qt, ql, qr;
	while(q--) {
		cin>>qt>>ql>>qr;
		/*for(int i=0;i<=n;i++) {
			cout<<i<<": "<<f(i, qt)<<"\n";
		}*/

		if(f(0, qt) < ql || f(n, qt) > qr) {
			cout<<"0\n";
			continue;
		}

		int index1 = n;
		for(int cekor=n/2;cekor>0;cekor/=2) {
			while(index1-cekor>=0 && f(index1-cekor, qt) <= qr) index1-=cekor;
		}

		int index2 = 0;
		for(int cekor=n/2;cekor>0;cekor/=2) {
			while(index2+cekor<=n && f(index2+cekor, qt) >= ql) index2+=cekor;
		}
		
		if(index1 > index2) swap(index1, index2);

		cout<<(index2-index1+1)<<"\n";
	}
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 81.0

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