QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#395215 | #1375. TripTik | megz112233 | AC ✓ | 8858ms | 335388kb | C++23 | 5.5kb | 2024-04-21 10:59:01 | 2024-04-21 10:59:01 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define bigint __int128
#define el '\n'
#define ll long long
#define int long long
//#define int long long
#define ld long double
using namespace std;
const int N = 1e5 + 4, M = 1e5 + 10, mod = 998244353;
int szz = 1;
struct seg_tree {
vector<vector<pair<int, int>>> tree;
// weight , idx
vector<pair<int, int>> neutral = {};
int k;
seg_tree(int n, vector<vector<pair<int, int>>> &v, int k) {
szz = 1;
while (szz < n)szz <<= 1;
tree.assign(2 * szz, neutral);
this->k = k;
build(v);
}
vector<pair<int, int>> merge(vector<pair<int, int>> val1, vector<pair<int, int>> val2) {
// vector 2*n 3,3
for (auto x: val2)val1.push_back(x);
sort(val1.rbegin(), val1.rend());
while (sz(val1) > k)val1.pop_back();
return val1;
}
void build(vector<vector<pair<int, int>>> &v, int node = 0, int lx = 0, int rx = szz - 1) {
if (lx == rx) {
if (lx < sz(v)) {
tree[node] = v[lx];
}
return;
}
int mid = lx + rx >> 1;
build(v, (node << 1) + 1, lx, mid);
build(v, (node << 1) + 2, mid + 1, rx);
tree[node] = merge(tree[(node << 1) + 1], tree[(node << 1) + 2]);
}
void set(int idx, vector<pair<int, int>> val, int node = 0, int lx = 0, int rx = szz - 1) {
if (lx == rx) {
tree[node] = val;
return;
}
int mid = (lx + rx) >> 1;
if (mid >= idx) {
set(idx, val, (node << 1) + 1, lx, mid);
} else {
set(idx, val, (node << 1) + 2, mid + 1, rx);
}
tree[node] = merge(tree[(node << 1) + 1], tree[(node << 1) + 2]);
}
vector<pair<int, int>> query(int l, int r, int node = 0, int lx = 0, int rx = szz - 1) {
if (lx > r or rx < l)return neutral;
if (lx >= l and rx <= r) {
return tree[node];
}
int mid = lx + rx >> 1;
vector<pair<int, int>> q1 = query(l, r, (node << 1) + 1, lx, mid);
vector<pair<int, int>> q2 = query(l, r, (node << 1) + 2, mid + 1, rx);
return merge(q1, q2);
}
};
void acc() {
int n, k;
cin >> n >> k;
// 0
vector<pair<long long , long long >> points(n);
// x-axis , idx
// -5 -1 0 1 2 3
for (int i = 0; i < n; i++) {
int x;
cin >> x;
points[i] = {x, i};
}
points.push_back({0, -1});
sort(points.begin(), points.end());
n++;
vector<vector<pair<int, int>>> v(n);
for (int i = 0; i < n; i++) {
v[i].push_back({points[i].second, i});
}
seg_tree sg(n, v, k);
int lg = 28;
vector<int> adj[n + 1][lg];
vector<int> pw(lg + 1, 1);
pw[0] = 0;
for (int i = 2; i < lg; i++)pw[i] = pw[i - 1] * 2;
for (int bt = 0; bt < lg; bt++) {
// cout << "with bt = " << bt << el;
// cout << "---------" << el;
for (int i = 0; i < n; i++) {
int l = points[i].first - pw[bt], r = points[i].first + pw[bt];
pair<long long ,long long > p = {l,-1};
int idxl = std::lower_bound(points.begin(), points.end(), p ) - points.begin();
p = {r,-1};
auto idxr = std::lower_bound(points.begin(), points.end(), p) - points.begin();
if (idxr == n or points[idxr].first > r)idxr--;
// cout << points[i].first << " " << idxl << " " << idxr << el;
vector<pair<int, int>> ret = sg.query(idxl, idxr);
// weight , idx
for (auto [val, idx]: ret) {
adj[i][bt].push_back(idx);
// cout << idx << " ";
}
// cout << "------" << el;
}
}
// for (int i = 0; i < n; i++) {
// cout << points[i].first << el;
// for (int j = 0; j < 4; j++) {
// cout << "with scoop == " << pw[j] << el;
// for (auto child: adj[i][j]) {
// cout << child << " ";
// }
// cout << el;
// }
// }
int idx_zero = -1;
for (int i = 0; i < sz(points); i++) {
if (points[i].first == 0)idx_zero = i;
}
priority_queue<array<int, 3>> pq;
// num_of operation , lst , bt
pq.push({0, idx_zero, 1});
vector<int> lst(n, 1e9);
vector<vector<int>> dist(n + 1, vector<int>(lg, 1e9));
dist[0][1] = 0;
while (sz(pq)) {
array<int, 3> arr = pq.top();
pq.pop();
int op = -arr[0], node = arr[1], bt = arr[2];
for (int i = 0; i < lg; i++) {
int nw_cost = abs(bt - i) + op;
for (auto child: adj[node][i]) {
if (dist[child][i] > nw_cost + (child != node)) {
dist[child][i] = nw_cost + (child != node);
pq.push({-dist[child][i], child, i});
}
if (child == node)lst[child] = min(lst[child], nw_cost);
}
}
}
vector<int> ans(n - 1, 11223344);
for (int i = 0; i < sz(points); i++) {
if (points[i].first == 0)continue;
ans[points[i].second] = lst[i];
}
for (int i = 0; i < sz(ans); i++) {
if (ans[i] >= 1e9)cout << "-1" << el;
else cout << ans[i] << el;
}
// cout << el;
}
signed main() {
int t = 1;
cout.tie(0);
cin.tie(0);
ios_base::sync_with_stdio(0);
// while (t--)acc();
acc();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3680kb
input:
4 2 -2 -1 -3 2
output:
3 1 3 2
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 5585ms
memory: 258300kb
input:
100000 4 -81032899 -96819000 35569221 67767248 74154777 75473369 3463319 18339682 -77145048 -26587182 -22902096 -55717109 -47237134 -44620229 -45753774 33183854 -15569807 72648777 -33842373 44545672 -48017305 71506102 33448860 -20688896 6205313 21527590 24985350 -14688810 29596074 -47051603 -9258675...
output:
56 49 48 47 47 50 38 42 -1 -1 51 55 51 52 51 46 41 48 46 44 47 47 49 44 37 -1 44 44 45 51 49 49 45 49 44 43 51 54 46 43 -1 44 49 57 46 45 43 47 46 53 48 44 47 -1 49 55 53 47 52 51 49 47 53 56 43 50 43 29 43 50 52 52 47 45 47 50 52 47 49 47 50 49 48 47 49 45 62 37 47 48 51 39 47 46 48 50 47 53 44 52 ...
result:
ok 100000 lines
Test #3:
score: 0
Accepted
time: 5601ms
memory: 257460kb
input:
100000 4 70680198 97317334 39546330 -54313602 -76555335 61941724 -8221943 -40467311 -38387353 -79352984 -85695884 -116744 -8014898 -90838613 21642942 -13906694 61034002 41083341 22631959 70997275 75121931 90712180 -50976024 -89714113 62620386 30945015 37854774 2964535 80028136 -28328113 -32257258 78...
output:
-1 59 -1 48 49 43 44 49 46 52 48 -1 45 49 40 45 47 43 46 54 -1 49 46 50 46 44 45 39 45 45 46 52 -1 37 52 49 33 42 42 -1 40 34 50 -1 47 56 50 54 -1 46 -1 44 50 37 -1 50 60 48 51 49 -1 53 47 44 41 -1 47 46 -1 50 47 47 48 51 46 47 44 51 50 48 -1 -1 40 48 -1 43 42 58 51 43 54 43 48 50 41 -1 45 48 48 55 ...
result:
ok 100000 lines
Test #4:
score: 0
Accepted
time: 5594ms
memory: 258380kb
input:
100000 4 -22911754 64514931 -46579963 -52307990 -28419918 -35238 66903391 -87096465 15648262 -88916963 96268224 -39583622 -33334243 76123224 30449894 -60512561 92205726 96701672 12953603 70508490 88259167 -12584810 35245713 2029713 19820003 91618921 -66864990 -96291681 73438998 6296068 -26195246 780...
output:
-1 50 45 48 45 22 46 52 46 59 52 52 47 50 52 49 50 48 -1 49 47 55 49 40 50 49 54 -1 48 41 43 41 46 55 -1 50 49 46 48 48 46 47 49 48 50 42 45 55 44 55 54 47 56 -1 52 55 -1 52 -1 54 48 -1 54 41 45 47 50 -1 50 56 48 57 44 48 50 50 48 -1 -1 55 52 53 57 51 45 57 51 45 49 54 52 42 48 57 49 49 51 57 47 51 ...
result:
ok 100000 lines
Test #5:
score: 0
Accepted
time: 8858ms
memory: 335388kb
input:
100000 4 -288 -318 -339 -525 -666 -688 714 -1068 1248 -1318 1453 1485 -1503 1767 1844 1893 -1903 -1942 -1959 1995 2114 -2150 -2209 2256 -2302 2317 -2414 -2423 2693 -2702 2736 -2948 2974 2986 3013 -3019 3197 -3300 3493 3495 3612 -3633 -3657 3702 3727 -3753 3758 4031 -4063 4131 -4172 -4284 4298 4409 4...
output:
11 11 10 11 11 11 11 12 13 13 14 14 13 15 15 15 15 15 15 14 14 15 15 14 14 14 14 14 16 15 16 15 15 16 15 15 16 15 18 17 17 15 15 16 15 15 15 16 17 16 16 16 16 15 15 16 15 16 16 16 16 16 19 17 17 16 16 17 18 17 17 17 16 18 18 16 18 17 18 18 16 17 16 17 16 16 16 16 16 18 19 17 17 17 17 18 17 17 18 17 ...
result:
ok 100000 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
2 1 -13 -20
output:
7 6
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 5026ms
memory: 252488kb
input:
100000 4 76 8621794 308 92 6 34 1 483450 375193 6822 11 86577381 975813 5025 9 63600034 459 2 738030 3518 24576 42 7850 56238 40826768 1775 40118 32 2802 44344 429383 162507 1017 628933 361842 49 419 12 1593123 876 156 26178 54984 6102 8073233 109434 16 13978897 134384 5 1560478 35 145007 100827 815...
output:
15 53 20 17 6 12 1 41 49 29 8 50 39 28 6 56 21 2 45 26 37 12 32 35 -1 27 -1 11 27 38 51 37 26 40 48 14 21 7 -1 23 19 35 35 32 -1 -1 9 44 52 4 41 11 49 41 64 39 18 36 43 18 25 46 25 36 11 31 11 45 70 46 47 50 12 26 32 35 8 40 -1 23 46 30 24 41 -1 42 -1 57 34 34 57 21 30 41 10 49 23 51 3 51 41 -1 38 1...
result:
ok 100000 lines
Test #8:
score: 0
Accepted
time: 4823ms
memory: 247440kb
input:
100000 4 245352 1 523 6520 1080897 1894 11174315 206582 27800445 43672882 1960 2037 12339783 197460 3208646 224604 109172 60481043 71 232890 3519534 23453 4356 103 439 20 97 6265775 167265 177 57 26965344 2228831 35719 154 1592499 308701 2 344 19657419 2598760 49175 13 401 26 736 4275 85118178 80666...
output:
42 1 20 42 -1 25 48 40 63 72 25 25 54 49 46 38 33 67 15 42 44 43 28 15 23 10 16 45 34 17 13 64 41 40 18 54 45 2 20 59 46 34 9 21 12 22 29 71 -1 35 12 55 -1 24 44 43 49 3 31 65 15 66 16 7 20 36 37 41 24 43 38 31 -1 36 42 23 35 55 66 50 38 60 12 43 17 40 66 62 44 28 7 20 21 50 69 46 39 43 46 30 72 42 ...
result:
ok 100000 lines
Test #9:
score: 0
Accepted
time: 4966ms
memory: 252576kb
input:
100000 4 889 21738495 59706 3859026 114 45 173111 6292802 2 117 13 11 13201 81386 51048924 79 42 6 26276509 36320 5621949 10 434 37 19683193 822970 6269807 50057532 9 15 24 18614267 22902213 1318 21 17403705 6828 14123 8958 2501 233101 1553 31308685 11413 73 2266252 1267501 86091802 7755 136705 20 1...
output:
22 45 33 39 16 12 49 -1 2 15 9 8 31 37 63 15 12 5 42 35 41 6 22 12 42 45 44 52 6 8 11 49 57 22 10 47 33 34 30 37 35 26 49 29 17 43 44 58 30 37 9 46 41 18 33 29 48 43 45 5 9 19 40 56 -1 17 47 62 49 1 48 43 32 30 33 42 38 15 38 14 47 39 4 37 40 43 61 38 46 45 -1 35 -1 30 40 52 30 46 39 -1 33 17 13 37 ...
result:
ok 100000 lines