QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#701326 | #5082. Frog Jump | tamthegod# | AC ✓ | 195ms | 51280kb | C++23 | 2.1kb | 2024-11-02 14:03:55 | 2024-11-02 14:04:00 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, k;
pair<int, int> a[maxN];
int b[maxN];
vector<pair<int, int>> adj[maxN];
void ReadInput()
{
cin >> n >> k;
for(int i=1; i<=n; i++)
cin >> a[i].fi >> a[i].se;
for(int i=1; i<=k; i++)
cin >> b[i];
}
int jump[maxN][21];
int depth[maxN];
int f[maxN];
void dfs(int u, int par)
{
for(auto [v, w] : adj[u])
{
if(v == par) continue;
depth[v] = depth[u] + 1;
f[v] = f[u] + w;
jump[v][0] = u;
for(int i=1; i<=18; i++)
jump[v][i] = jump[jump[v][i - 1]][i - 1];
dfs(v, u);
}
}
int lca(int u, int v)
{
if(depth[u] < depth[v]) swap(u, v);
int k = depth[u] - depth[v];
for(int i=18; i>=0; i--)
if(k >> i & 1) u = jump[u][i];
if(u == v) return u;
for(int i=18; i>=0; i--)
if(jump[u][i] != jump[v][i])
{
u = jump[u][i];
v = jump[v][i];
}
return jump[u][0];
}
int dist(int u, int v)
{
return f[u] + f[v] - 2 * f[lca(u, v)];
}
void Solve()
{
int id = 1;
for(int i=2; i<=n; i++)
{
adj[id].pb({i, max(0ll, a[i].fi - a[id].se)});
adj[i].pb({id, max(0ll, a[i].fi - a[id].se)});
if(a[i].se > a[id].se) id = i;
}
dfs(1, 0);
b[0] = 1;
int res = 0;
for(int i=1; i<=k; i++)
res += dist(b[i - 1], b[i]);
cout << res;
}
#define taskname "sol"
int32_t main()
{
if (fopen(taskname ".inp", "r"))
{
freopen(taskname ".inp", "r", stdin);
//freopen(taskname ".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
//cin >> T;
for(int itest=1; itest<=T; itest++)
{
ReadInput();
Solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9760kb
input:
4 3 0 2 0 3 3 5 6 7 4 2 3
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 2ms
memory: 9716kb
input:
4 3 0 2 0 3 3 5 6 7 2 3 2
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 2ms
memory: 9964kb
input:
8 5 1 8 2 4 5 11 13 15 15 17 16 18 19 22 20 22 3 7 4 6 3
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 2ms
memory: 9708kb
input:
8 5 1 5 5 10 10 15 15 20 20 25 25 30 30 35 35 40 3 7 4 6 3
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 9712kb
input:
10 7 1 5 5 10 10 15 15 20 20 25 25 30 30 35 35 40 41 50 50 60 3 7 4 6 3 9 10
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 2ms
memory: 9836kb
input:
10 10 1 5 5 10 10 15 15 20 20 25 25 30 30 35 35 40 41 50 50 60 3 7 4 6 3 9 10 5 1 9
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 2ms
memory: 9820kb
input:
6 11 0 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 5 4 3 2 1
output:
10
result:
ok single line: '10'
Test #8:
score: 0
Accepted
time: 0ms
memory: 9912kb
input:
13 14 0 2 1 3 2 4 4 6 10 15 11 13 12 15 20 25 27 29 28 30 33 35 34 36 35 37 3 4 8 11 13 8 6 10 4 7 9 10 9 9
output:
53
result:
ok single line: '53'
Test #9:
score: 0
Accepted
time: 0ms
memory: 9836kb
input:
14 25 0 22 1 5 5 10 12 16 14 20 20 24 27 33 30 38 34 40 34 45 47 53 49 55 55 60 60 65 2 5 4 6 10 8 7 9 12 11 14 13 9 10 7 8 4 5 1 2 6 5 3 8 10
output:
13
result:
ok single line: '13'
Test #10:
score: 0
Accepted
time: 2ms
memory: 9912kb
input:
14 25 0 22 1 5 5 10 12 16 14 20 20 24 27 33 30 38 34 40 34 45 47 53 49 55 55 60 60 65 2 5 4 6 5 1 3 2 6 5 1 1 3 2 2 5 6 6 1 2 3 4 4 5 2
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 22ms
memory: 45220kb
input:
100000 100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
output:
99999
result:
ok single line: '99999'
Test #12:
score: 0
Accepted
time: 84ms
memory: 49232kb
input:
100000 1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
output:
1899981
result:
ok single line: '1899981'
Test #13:
score: 0
Accepted
time: 75ms
memory: 50852kb
input:
100000 1000000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51...
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 63ms
memory: 50760kb
input:
100000 1000000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51...
output:
1710000
result:
ok single line: '1710000'
Test #15:
score: 0
Accepted
time: 82ms
memory: 47132kb
input:
100000 1000000 0 1 1000 1001 2000 2001 3000 3001 4000 4001 5000 5001 6000 6001 7000 7001 8000 8001 9000 9001 10000 10001 11000 11001 12000 12001 13000 13001 14000 14001 15000 15001 16000 16001 17000 17001 18000 18001 19000 19001 20000 20001 21000 21001 22000 22001 23000 23001 24000 24001 25000 25001...
output:
1898081019
result:
ok single line: '1898081019'
Test #16:
score: 0
Accepted
time: 77ms
memory: 51216kb
input:
100000 1000000 0 1 1000 1001 2000 2001 3000 3001 4000 4001 5000 5001 6000 6001 7000 7001 8000 8001 9000 9001 10000 10001 11000 11001 12000 12001 13000 13001 14000 14001 15000 15001 16000 16001 17000 17001 18000 18001 19000 19001 20000 20001 21000 21001 22000 22001 23000 23001 24000 24001 25000 25001...
output:
99898901100999
result:
ok single line: '99898901100999'
Test #17:
score: 0
Accepted
time: 79ms
memory: 48504kb
input:
100000 1000000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51...
output:
89999910000
result:
ok single line: '89999910000'
Test #18:
score: 0
Accepted
time: 80ms
memory: 51244kb
input:
100000 1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...
output:
99998900001
result:
ok single line: '99998900001'
Test #19:
score: 0
Accepted
time: 154ms
memory: 49308kb
input:
100000 1000000 0 1 1000 1001 2000 2001 3000 3001 4000 4001 5000 5001 6000 6001 7000 7001 8000 8001 9000 9001 10000 10001 11000 11001 12000 12001 13000 13001 14000 14001 15000 15001 16000 16001 17000 17001 18000 18001 19000 19001 20000 20001 21000 21001 22000 22001 23000 23001 24000 24001 25000 25001...
output:
23393761453368
result:
ok single line: '23393761453368'
Test #20:
score: 0
Accepted
time: 164ms
memory: 50816kb
input:
100000 1000000 0 1 1000 1001 2000 2001 3000 3001 4000 4001 5000 5001 6000 6001 7000 7001 8000 8001 9000 9001 10000 10001 11000 11001 12000 12001 13000 13001 14000 14001 15000 15001 16000 16001 17000 17001 18000 18001 19000 19001 20000 20001 21000 21001 22000 22001 23000 23001 24000 24001 25000 25001...
output:
36210751926075
result:
ok single line: '36210751926075'
Test #21:
score: 0
Accepted
time: 114ms
memory: 42124kb
input:
100000 1000000 250 77313008 639 795104759 4914 260482167 7347 587490367 10804 17115580 12197 335448455 12252 592081936 12633 893562902 21551 651916319 27051 470581984 28774 881490168 35517 16417220 39058 21328451 41337 483500381 43756 740464747 45842 411312383 47619 401055682 56006 706089931 57490 7...
output:
0
result:
ok single line: '0'
Test #22:
score: 0
Accepted
time: 111ms
memory: 42788kb
input:
100000 1000000 282 107048439 4403 305378629 13402 27000377 17818 408950410 18928 428924854 19409 92912943 28529 47724576 31476 242244483 31899 199510232 41280 14659285 41451 300049859 44110 465583588 47274 266197817 50361 166975418 54823 18976096 69975 451791096 79504 329580164 80341 399743786 84373...
output:
2029128948
result:
ok single line: '2029128948'
Test #23:
score: 0
Accepted
time: 195ms
memory: 41992kb
input:
100000 1000000 13286 94927 28911 355597 44215 337605 66747 718864 67667 338138 72806 709992 73242 809197 89489 656349 107058 693816 108707 798596 109030 478427 119237 416935 129997 438974 133032 141755 134534 833011 137875 580040 143284 530014 147134 412870 147426 303891 148649 148916 149680 227674 ...
output:
3758886268357
result:
ok single line: '3758886268357'
Test #24:
score: 0
Accepted
time: 180ms
memory: 44112kb
input:
100000 1000000 3009 785588 4965 602298 17211 594326 25231 369145 25926 319526 41977 814433 43538 622870 45913 553408 65345 440774 70173 819844 75787 976652 80081 325874 82016 199506 82771 522115 86631 518196 87109 295202 90333 270431 97113 205312 105567 201324 111895 636283 112324 771941 112829 5926...
output:
3636123778070
result:
ok single line: '3636123778070'
Test #25:
score: 0
Accepted
time: 164ms
memory: 50512kb
input:
100000 1000000 2997 3473 6431 6472 7509 8026 9973 10201 19486 19798 45906 46278 51526 51890 56163 57085 63369 63476 91820 92034 94937 95107 111336 112235 111359 111543 116843 117662 117615 118223 120566 121138 130978 131159 135561 136446 147970 148695 150404 151133 157882 158208 168461 169014 169551...
output:
317303027980377
result:
ok single line: '317303027980377'
Test #26:
score: 0
Accepted
time: 154ms
memory: 49304kb
input:
100000 1000000 80 556 1333 1659 4603 5314 12840 13686 15011 15181 19980 20540 33688 34290 57242 57503 70639 71150 70744 71443 70973 71933 101402 102029 122114 122634 149151 149971 149232 149740 162030 162332 166814 167536 184607 184795 189647 189902 197599 197855 201010 201412 224780 224910 227237 2...
output:
317104704899621
result:
ok single line: '317104704899621'
Test #27:
score: 0
Accepted
time: 165ms
memory: 51224kb
input:
100000 1000000 1717 1765 11046 11107 17253 17297 25857 25936 29711 29783 29749 29830 35862 35886 37943 37977 40099 40125 41923 42009 43138 43220 78301 78386 105727 105728 124193 124223 127196 127224 133389 133425 152825 152849 190329 190395 195691 195696 202784 202802 225104 225186 238917 238951 241...
output:
331650548522090
result:
ok single line: '331650548522090'
Test #28:
score: 0
Accepted
time: 29ms
memory: 40920kb
input:
100000 1000 7851 8791 12355 13251 13151 13446 15759 16642 24880 25767 35488 36428 56300 56716 59693 60278 68111 68299 71408 72162 79308 79822 84768 85452 87651 88362 99750 100511 107186 108030 114319 114871 126879 127878 133554 134113 136987 137153 146364 147164 159232 160019 163648 164500 197322 19...
output:
313797403920
result:
ok single line: '313797403920'
Test #29:
score: 0
Accepted
time: 15ms
memory: 43176kb
input:
100000 1000 19170 19256 30381 30448 47822 47901 65757 65829 68119 68148 85396 85459 98157 98240 101806 101871 108550 108578 112334 112401 147580 147632 149283 149316 150660 150685 155865 155947 174229 174310 176061 176135 177889 177968 178645 178717 179606 179622 181791 181826 183977 183996 195996 1...
output:
336875518213
result:
ok single line: '336875518213'
Test #30:
score: 0
Accepted
time: 16ms
memory: 43080kb
input:
100000 10 9547 9577 15758 15851 22811 22869 32761 32811 86666 86709 102010 102077 107437 107473 109369 109382 142354 142434 143977 143984 145739 145837 154379 154392 159026 159030 172130 172220 176096 176118 181457 181504 195326 195374 199221 199309 212097 212150 212786 212791 229444 229467 241264 2...
output:
3020261398
result:
ok single line: '3020261398'
Test #31:
score: 0
Accepted
time: 156ms
memory: 51280kb
input:
100000 1000000 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 5...
output:
210936267000
result:
ok single line: '210936267000'
Test #32:
score: 0
Accepted
time: 158ms
memory: 51020kb
input:
100000 1000000 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 5...
output:
210893031000
result:
ok single line: '210893031000'
Test #33:
score: 0
Accepted
time: 138ms
memory: 51044kb
input:
100000 1000000 1 11 2 12 7 17 19 29 20 30 31 41 33 43 36 46 37 47 47 57 58 68 73 83 81 91 87 97 92 102 103 113 123 133 132 142 139 149 142 152 144 154 145 155 146 156 148 158 150 160 160 170 163 173 165 175 166 176 171 181 172 182 175 185 176 186 179 189 183 193 184 194 188 198 189 199 191 201 200 2...
output:
226951152313
result:
ok single line: '226951152313'
Test #34:
score: 0
Accepted
time: 153ms
memory: 50276kb
input:
100000 1000000 4 14 5 15 14 24 15 25 24 34 30 40 33 43 35 45 37 47 42 52 49 59 61 71 62 72 65 75 69 79 70 80 71 81 73 83 79 89 82 92 85 95 86 96 94 104 101 111 104 114 107 117 113 123 122 132 123 133 126 136 127 137 136 146 139 149 141 151 147 157 151 161 153 163 155 165 157 167 161 171 163 173 171 ...
output:
227419516389
result:
ok single line: '227419516389'
Test #35:
score: 0
Accepted
time: 79ms
memory: 44320kb
input:
100000 1000000 0 1000000000 4 14 5 15 14 24 15 25 24 34 30 40 33 43 35 45 37 47 42 52 49 59 61 71 62 72 65 75 69 79 70 80 71 81 73 83 79 89 82 92 85 95 86 96 94 104 101 111 104 114 107 117 113 123 122 132 123 133 126 136 127 137 136 146 139 149 141 151 147 157 151 161 153 163 155 165 157 167 161 171...
output:
0
result:
ok single line: '0'