Submission #43976

#	Time	Username	Problem	Language	Result	Execution time	Memory
43976		wzy	Worst Reporter 3 (JOI18_worst_reporter3)	C++11	100 / 100	1714 ms	11692 KiB

worst_reporter3

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n , q;	
int d[1000000];
int x[1000000];
int read(){
	char c;
	int a = 0;
	while(!(c >= '0' && c <= '9')) c = getchar();
	while(c >= '0' && c<='9'){
		a = 10*a + (c - '0');
		c =getchar();
	}
	return a;
}

int cima(int i , int j){
	if(i%j) return i/j + 1;
	else return i/j;
}


int32_t main(){
	n = read() , q  =read();
	for(int i = 1 ; i <= n; i++) d[i] = read();
	x[1] = d[1];
	for(int i = 2 ; i <= n; i++){
		x[i] = (x[i-1]) * (cima(d[i] , x[i-1]));
	}
	while(q--){
		int l , r ,t; 
		t = read();
		int def = 0;
		l = read() , r = read();
		int ll = 1 , rr = n;
		int ansj = n+1;
		if(l <= t && t <= r) def++;
		while(ll<=rr) {
			int mid = (ll+rr)/2;
			int p = t / x[mid];
			if(p*x[mid] - mid < l){
				ansj  = mid;
				rr = mid - 1;
			}
			else ll = mid + 1;
		}
		int ansj2 =0;
		ll = 1 , rr = n;
		while(ll<=rr){
			int mid = (ll+rr)/2;
			int p = t/x[mid];
			if(p*x[mid] - mid > r){
				ansj2 = mid ;
				ll = mid + 1;
			}
			else rr = mid - 1;
		}
		 def += n;
		if(ansj2) def -= ansj2;
		if(ansj != (n + 1)){
			def -= (n - ansj + 1);
		}
		cout<<def<<endl;
	}
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'long long int read()':
worst_reporter3.cpp:10:8: warning: 'c' is used uninitialized in this function [-Wuninitialized]
  while(!(c >= '0' && c <= '9')) c = getchar();
        ^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 81 / 81