oj.uz

Submission #225191

# Submission time Handle Problem Language Result Execution time Memory
225191 2020-04-19T13:41:21 Z kshitij_sodani Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 1580 ms 25856 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
typedef long long llo;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,q;
	llo aa;
	cin>>n>>q;
	vector<llo> bb;
	bb.pb(1);
	for(llo i=0;i<n;i++){
		cin>>aa;
		llo cc=bb[bb.size()-1];
		llo dd=(aa/cc)*cc;
		if(aa%cc>0){
			dd+=cc;
		}
		bb.pb(dd);
	//	cout<<dd<<" ";
	}
//	cout<<endl;

	llo tt,l,r;
	while(q--){
		cin>>tt>>l>>r;
		if(tt<l){
			cout<<0<<endl;
			continue;

		}
		llo ma=tt-tt%bb[bb.size()-1]-(bb.size());
		if(ma>r){
			cout<<0<<endl;
			continue;
		}
		llo low=0;
		llo high=bb.size()-1;
		while(low<high-1){
			llo mid=(low+high)/2;
			llo val=tt-tt%bb[mid]-mid;
			if(val<l){
				high=mid;
			}
			else{
				low=mid;
			}
		}
		llo ind2;
		llo val2=tt-tt%bb[high]-high;

		//cout<<low<<" "<<high<<" "<<val2<<endl;
		if(val2<l){
			ind2=low;
		}
		else{
			ind2=high;
		}

		low=0;
		high=bb.size()-1;
		while(low<high-1){
			llo mid=(low+high)/2;
			llo val=tt-tt%bb[mid]-mid;
			if(val>r){
				low=mid;
			}
			else{
				high=mid;
			}
		}
		llo ind3;
		llo val3=tt-tt%bb[low]-low;
		if(val3>r){
			ind3=high;
		}
		else{
			ind3=low;
		}
	//	cout<<ind3<<" "<<ind2<<endl;
		cout<<ind2-ind3+1<<endl;
	}





	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1569 ms 23092 KB Output is correct
2 Correct 1577 ms 23020 KB Output is correct
3 Correct 1549 ms 22880 KB Output is correct
4 Correct 1531 ms 23160 KB Output is correct
5 Correct 1526 ms 23008 KB Output is correct
6 Correct 1580 ms 23024 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1569 ms 23092 KB Output is correct
2 Correct 1577 ms 23020 KB Output is correct
3 Correct 1549 ms 22880 KB Output is correct
4 Correct 1531 ms 23160 KB Output is correct
5 Correct 1526 ms 23008 KB Output is correct
6 Correct 1580 ms 23024 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 7 ms 256 KB Output is correct
12 Correct 7 ms 384 KB Output is correct
13 Correct 1341 ms 21724 KB Output is correct
14 Correct 1333 ms 22236 KB Output is correct
15 Correct 1310 ms 20624 KB Output is correct
16 Correct 1323 ms 21360 KB Output is correct
17 Correct 1450 ms 25568 KB Output is correct
18 Correct 1469 ms 25856 KB Output is correct
19 Correct 1475 ms 25632 KB Output is correct
20 Correct 1457 ms 25532 KB Output is correct
21 Correct 1451 ms 25568 KB Output is correct
22 Correct 1422 ms 25660 KB Output is correct
23 Correct 1438 ms 25640 KB Output is correct
24 Correct 1491 ms 25568 KB Output is correct
25 Correct 1562 ms 22904 KB Output is correct
26 Correct 1577 ms 23008 KB Output is correct
27 Correct 1479 ms 25032 KB Output is correct
28 Correct 1508 ms 25564 KB Output is correct
29 Correct 1493 ms 24928 KB Output is correct
30 Correct 1527 ms 25220 KB Output is correct
31 Correct 1469 ms 25444 KB Output is correct
32 Correct 1456 ms 21600 KB Output is correct
33 Correct 5 ms 384 KB Output is correct