Submission #414913

#	Time	Username	Problem	Language	Result	Execution time	Memory
414913		Pro_ktmr	Worst Reporter 3 (JOI18_worst_reporter3)	C++17	100 / 100	1099 ms	37088 KiB

worst_reporter3

#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl
#else
#define debug(x)
#endif
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

const ll INF = 2e9;

int N, Q;
ll D[500000];

ll a[500001], b[500001]; // 人 i が k 回目 (k >= 0) に止まるのは x = ak + b
ll c[500001]; // 人 i が k 回目 (k >= 0) に動くときの時刻は t = ck

int binarySearch(ll t, ll x){ // 時刻 t に座標 x 以下にいる人の中で最も右にいる人の番号
	int ok = N+1;
	int ng = -1;
	while(ok-ng > 1){
		int m = (ok+ng)/2;
		ll k = t/c[m];
		if(a[m]*k + b[m] <= x) ok = m;
		else ng = m;
	}
	return ok;
}

signed main(){
	scanf("%d%d", &N, &Q);
	rep(i, N) scanf("%lld", D+i);

	a[0] = 1;
	b[0] = 0;
	c[0] = 1;
	rep(i, N+1){
		if(i == 0) continue;
		b[i] = -i;
		ll f = (D[i-1]+a[i-1]-1) / a[i-1]; // 人 i-1 が f 回進んだら自分も進む
		f = min(f, INF);
		a[i] = min(f*a[i-1], INF);
		c[i] = min(f*c[i-1], INF);
	}

	rep(i, Q){
		int T, L, R;
		scanf("%d%d%d", &T, &L, &R);
		//cout << binarySearch(T, L-1) << " " << binarySearch(T, R) << endl;
		printf("%d\n", binarySearch(T, L-1) - binarySearch(T, R));
	}
}

Compilation message (stderr)

worst_reporter3.cpp: In function 'int main()':
worst_reporter3.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
worst_reporter3.cpp:39:2: note: in expansion of macro 'rep'
   39 |  rep(i, N) scanf("%lld", D+i);
      |  ^~~
worst_reporter3.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
worst_reporter3.cpp:44:2: note: in expansion of macro 'rep'
   44 |  rep(i, N+1){
      |  ^~~
worst_reporter3.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
worst_reporter3.cpp:53:2: note: in expansion of macro 'rep'
   53 |  rep(i, Q){
      |  ^~~
worst_reporter3.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
worst_reporter3.cpp:39:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  rep(i, N) scanf("%lld", D+i);
      |            ~~~~~^~~~~~~~~~~~~
worst_reporter3.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d%d", &T, &L, &R);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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