QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#514792 | #7845. Fast Forward | Umok | RE | 1ms | 5992kb | C++14 | 1.4kb | 2024-08-11 10:46:26 | 2024-08-11 10:46:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int long long
#define uint unsigned long long
#define lb(x) (x & (-x))
#define endl '\n'
#define INF LONG_LONG_MAX
#define eps 1e-7
const int N = 1e6 + 5;
typedef pair<int, int> PII;
int ar[N * 2], len = 21;
int st[3 * N][25];
void solve()
{
int n, m;
cin >> n >> m;
len = log(n) / log(2) + 1;
for (int i = 1; i <= n; i++)
cin >> ar[i], ar[i + n] = ar[i];
for (int i = 1; i <= 2 * n; i++)
ar[i] += ar[i - 1];
for (int i = 0; i <= len; i++)
st[2 * n + 1][i] = INF;
for (int i = 1; i <= 2 * n; i++)
{
int l = i - 1, r = 2 * n;
while (l + 1 < r)
{
int mid = (l + r) >> 1;
if (ar[mid] - ar[i - 1] >= m)
r = mid;
else
l = mid;
}
st[i][0] = r + 1;
}
for (int j = 1; j <= len; j++)
for (int i = 1; i <= 2 * n; i++)
st[i][j] = st[st[i][j - 1]][j - 1];
for (int i = 1; i <= n; i++)
{
int ans = 0;
int t = i;
for (int j = len - 1; j >= 0; j--)
{
if (st[t][j] < i + n)
{
t = st[t][j];
ans += 1 << j;
}
}
cout << ans << " ";
}
}
signed main()
{
IOS;
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5860kb
input:
7 7 1 1 1 1 1 1 1
output:
0 0 0 0 0 0 0
result:
ok single line: '0 0 0 0 0 0 0 '
Test #2:
score: 0
Accepted
time: 1ms
memory: 5788kb
input:
3 3 1 1 3
output:
0 1 1
result:
ok single line: '0 1 1 '
Test #3:
score: 0
Accepted
time: 1ms
memory: 5992kb
input:
10 5 4 1 5 5 1 3 2 1 5 2
output:
5 4 5 4 4 5 4 4 5 4
result:
ok single line: '5 4 5 4 4 5 4 4 5 4 '
Test #4:
score: -100
Runtime Error
input:
1000000 22867 553 901 645 485 940 745 166 365 357 935 102 534 812 329 56 650 100 992 528 829 755 128 190 916 245 942 132 359 367 562 636 77 62 562 404 487 545 298 71 697 784 523 957 383 332 650 636 822 245 379 792 605 239 69 723 867 925 308 511 975 808 341 341 125 940 833 810 282 567 754 893 59 618 ...