oj.uz

Submission #414913

# Submission time Handle Problem Language Result Execution time Memory
414913 2021-05-31T10:35:49 Z Pro_ktmr Worst Reporter 3 (JOI18_worst_reporter3) C++17
100 / 100
 1099 ms 37088 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 34296 KB Output is correct
2 Correct 1076 ms 34328 KB Output is correct
3 Correct 960 ms 34412 KB Output is correct
4 Correct 986 ms 34292 KB Output is correct
5 Correct 970 ms 34292 KB Output is correct
6 Correct 1041 ms 34360 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 34296 KB Output is correct
2 Correct 1076 ms 34328 KB Output is correct
3 Correct 960 ms 34412 KB Output is correct
4 Correct 986 ms 34292 KB Output is correct
5 Correct 970 ms 34292 KB Output is correct
6 Correct 1041 ms 34360 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 312 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 527 ms 32936 KB Output is correct
14 Correct 532 ms 33368 KB Output is correct
15 Correct 488 ms 32068 KB Output is correct
16 Correct 555 ms 32676 KB Output is correct
17 Correct 660 ms 36892 KB Output is correct
18 Correct 702 ms 36820 KB Output is correct
19 Correct 658 ms 36924 KB Output is correct
20 Correct 673 ms 36880 KB Output is correct
21 Correct 696 ms 36892 KB Output is correct
22 Correct 717 ms 36952 KB Output is correct
23 Correct 623 ms 36884 KB Output is correct
24 Correct 626 ms 37088 KB Output is correct
25 Correct 1039 ms 34356 KB Output is correct
26 Correct 1099 ms 34372 KB Output is correct
27 Correct 825 ms 36388 KB Output is correct
28 Correct 706 ms 36788 KB Output is correct
29 Correct 787 ms 36272 KB Output is correct
30 Correct 760 ms 36516 KB Output is correct
31 Correct 772 ms 36632 KB Output is correct
32 Correct 801 ms 32988 KB Output is correct
33 Correct 1 ms 204 KB Output is correct