#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
const int MAXN = 200000;
int _R;
int ans;
class Seg{
private:
long long arr[MAXN*4+5];
long long tag[MAXN*4+5];
void pull(int now) {
arr[now] = arr[now*2] + arr[now*2+1];
}
void push(int now, int len) {
if (!tag[now]) return;
arr[now] += tag[now] * len;
if (len > 1) {
tag[now*2 ] += tag[now];
tag[now*2+1] += tag[now];
}
tag[now] = 0;
}
public:
void build(int now=1, int l=0, int r=_R-1) {
if (l == r) {
arr[now] = tag[now] = 0;
return;
}
int mid = l + r >> 1;
build(now*2 , l, mid);
build(now*2+1,mid+1,r);
pull(now);
}
void mdy(int ml, int mr, int v, int now=1, int l=0, int r=_R-1) {
push(now, r-l+1);
if (ml <= l && r <= mr) {
tag[now] += v;
push(now, r-l+1);
return;
} else if (l > mr || r < ml) return;
int mid = l + r >> 1;
mdy(ml, mr, v, now*2 , l, mid);
mdy(ml, mr, v, now*2+1,mid+1,r);
pull(now);
}
long long qry(int ql, int qr, int now=1, int l=0, int r=_R-1) {
push(now, r-l+1);
if (ql <= l && r <= qr) {
return arr[now];
} else if (l > qr || r < ql) return 0;
int mid = l + r >> 1;
long long sum = 0;
sum += qry(ql, qr, now*2 , l, mid);
sum += qry(ql, qr, now*2+1,mid+1,r);
pull(now);
return sum;
}
} seg;
int solve(int p, long long B) {
int l = p, r = _R-1, mid;
while (l < r) {
mid = (l + r + 1) >> 1;
if (seg.qry(p, mid) <= B)
l = mid;
else
r = mid - 1;
}
return l - p + 1;
}
int besthub(int R, int L, int X[], long long B) {
_R = R;
ans = 1;
seg.build();
for (int i = 1; i < R; i++)
seg.mdy(i, i, X[i] - X[0]);
int nowL = 0;
for (int i = 0; i < R; i++) {
int v = solve(nowL, B);
while (nowL < i) {
if (solve(nowL+1, B) >= v)
nowL++;
else
break;
}
ans = max(ans, solve(nowL, B));
if (i+1 < R) {
seg.mdy(0, i, X[i+1] - X[i]);
seg.mdy(i+1, R-1, X[i] - X[i+1]);
}
}
return ans;
}
Compilation message
ricehub.cpp: In member function 'void Seg::build(int, int, int)':
ricehub.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid = l + r >> 1;
| ~~^~~
ricehub.cpp: In member function 'void Seg::mdy(int, int, int, int, int, int)':
ricehub.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid = l + r >> 1;
| ~~^~~
ricehub.cpp: In member function 'long long int Seg::qry(int, int, int, int, int)':
ricehub.cpp:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
288 ms |
1488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
