QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#384702 | #4496. Shinobu Loves Segment Tree | Tobo# | AC ✓ | 103ms | 3620kb | C++20 | 1.5kb | 2024-04-10 10:44:02 | 2024-04-10 10:44:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--)
{
long long n, x;
cin >> n >> x;
if (x == 1)
{
cout << n * (n + 1) / 2 << '\n';
continue;
}
if (n == 1)
{
cout << 0 << '\n';
continue;
}
vector<int> path;
while (x > 1)
{
path.push_back(x & 1);
x >>= 1;
}
reverse(path.begin(), path.end());
auto dfs1 = [&](auto &dfs1, long long n, int dep)
{
if (dep == path.size())
return n;
if (n < 2)
return 0ll;
return path[dep] ? dfs1(dfs1, n / 2, dep + 1) : dfs1(dfs1, (n + 1) / 2, dep + 1);
};
auto dfs2 = [&](auto &dfs2, long long l, long long r, int dep)
{
if (dep == path.size())
return (r - l + 1) * (l + r) / 2;
if (l == 1ll)
l++;
if (l > r)
return 0ll;
long long res = 0;
if (!path[dep])
l++, r++;
res = dfs2(dfs2, l / 2, r / 2, dep + 1) * 2;
if (l % 2 == 1)
res -= dfs1(dfs1, l / 2, dep + 1);
if (r % 2 == 0)
res -= dfs1(dfs1, r / 2, dep + 1);
return res;
};
cout << dfs2(dfs2, 1, n, 0) << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 103ms
memory: 3620kb
input:
100000 249 707 360 1429 151 380 118 103 221 711 88 79 471 1668 222 377 481 676 483 921 326 558 347 1151 104 220 91 97 258 250 446 122 368 1335 242 335 395 470 180 669 99 222 342 979 345 431 119 97 283 781 325 643 488 1413 285 868 205 723 118 115 397 526 432 1557 197 761 145 287 304 270 331 243 98 36...
output:
0 0 0 61 0 28 0 64 151 176 0 0 11 58 230 1585 0 0 192 0 0 0 100 108 0 0 0 0 0 70 0 0 0 0 64 328 0 808 390 0 0 0 35 0 63 128 405 0 0 52 0 0 146 0 48 662 0 0 0 0 72 6757 0 15 63 150 30 6 66 0 0 236 0 459 100 0 63 0 0 105 0 81 34 0 0 208 0 0 2484 0 63 71 198 89 172 83 19 160 0 237 0 0 0 28 423 32 0 220...
result:
ok 100000 lines