QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722278 | #5415. Ropeway | Repeater# | AC ✓ | 890ms | 119148kb | C++20 | 2.5kb | 2024-11-07 18:26:55 | 2024-11-07 18:26:55 |
Judging History
answer
#include<iostream>
using namespace std;
#include<vector>
#include<string>
using i64 = long long;
const int N = 5e5 + 10;
vector<int> Log(N);
void init(){
Log[1] = 0;
for(int i = 2; i < N; ++i){
Log[i] = Log[i >> 1] + 1;
}
return;
}
void build(vector<i64>& a, vector<vector<i64>>& st){
st.assign(a.size(), vector<i64>(Log[a.size()] + 1));
for(int i = 0; i < a.size(); ++i) st[i][0] = a[i];
for(int i = 1; i <= Log[a.size()]; ++i){
int d = 1 << (i - 1);
for(int j = 0; j + (1 << i) - 1 < a.size(); ++j){
st[j][i] = min(st[j][i - 1], st[j + d][i - 1]);
}
}
return;
}
i64 tquery(int l, int r, vector<vector<i64>>& st){
int L = Log[r - l + 1];
return min(st[l][L], st[r - (1 << L) + 1][L]);
}
void solve(){
i64 n, k;
cin >> n >> k;
vector<i64> a(n + 1);
for(int i = 1; i <= n; ++i) cin >> a[i];
string s;
cin >> s;
vector<i64> pref(n + 2), suff(n + 2);
vector<i64> q(n + 2);
int l = 0, r = -1;
q[++r] = 0;
for(int i = 1; i <= n + 1; ++i){
pref[i] = a[i] + pref[q[l]];
if(i != n + 1){
if(s[i - 1] == '0')
while(l <= r && pref[q[r]] >= pref[i]) --r;
else r = l - 1;
q[++r] = i;
while(l <= r && i - q[l] >= k) ++l;
}
}
l = 0, r = -1;
q[++r] = n + 1;
for(int i = n; i >= 0; --i){
suff[i] = a[i] + suff[q[l]];
if(i != 0){
if(s[i - 1] == '0')
while(l <= r && suff[q[r]] >= suff[i]) --r;
else r = l - 1;
q[++r] = i;
while(l <= r && q[l] - i >= k) ++l;
}
}
vector<vector<i64>> st;
build(pref, st);
vector<i64> fn(n + 2), sn(n + 2);
int t1 = 0, t2 = n + 1;
for(int i = 1; i <= n; ++i){
if(s[i - 1] == '1') t1 = i;
if(s[n - i] == '1') t2 = n - i + 1;
fn[i] = t1;
sn[n - i + 1] = t2;
}
int query = 0;
cin >> query;
for(int i = 0; i < query; ++i){
i64 p, v;
cin >> p >> v;
i64 ans = pref[p] + suff[p] - 2 * a[p] + v;
if(s[p - 1] == '0')
for(int j = p + 1; j <= min(p + k - 1, min(sn[p], n + 1)); ++j){
ans = min(ans, tquery(max(0LL, max(fn[p], j - k)), p - 1, st) + suff[j]);
}
cout << ans << "\n";
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while(t--) solve();
return 0;
}
/*
3
10 3
5 10 7 100 4 3 12 5 100 1
0001000010
2
2 3
6 15
5 6
1 1 1 1 1
00000
1
3 100
5 6
1 1 1 1 1
00100
1
3 100
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5156kb
input:
3 10 3 5 10 7 100 4 3 12 5 100 1 0001000010 2 2 3 6 15 5 6 1 1 1 1 1 00000 1 3 100 5 6 1 1 1 1 1 00100 1 3 100
output:
206 214 0 100
result:
ok 4 number(s): "206 214 0 100"
Test #2:
score: 0
Accepted
time: 3ms
memory: 5164kb
input:
500 19 6 285203460 203149294 175739375 211384407 323087820 336418462 114884618 61054702 243946442 19599175 51974474 285317523 222489944 26675167 300331960 1412281 324105264 33722550 169011266 1111111110110100011 18 3 127056246 5 100630226 14 301161052 2 331781882 5 218792226 2 190274295 12 49227476 ...
output:
2472886431 2299111966 2796055445 2650202148 2417273966 2508694561 2285479513 2521569560 2521569560 2240907690 2577284958 2521569560 2766700195 2511807344 2521569560 2438434986 2669077215 2682112324 470735446 470735446 211705888 564509290 715543137 470735446 470735446 18 19 19 19 20 19 54 849950346 8...
result:
ok 5277 numbers
Test #3:
score: 0
Accepted
time: 4ms
memory: 5160kb
input:
50 183 160 22617237 21369258 39718669 4582413 28629717 25947766 1690897 19844235 35568283 42909820 21829213 70588436 8472484 53107624 21547259 11440081 6630789 5896457 19770793 30204510 29796593 27689811 39350369 21646987 36362667 38164292 13428410 54681069 24526477 58941286 70890011 43730474 388615...
output:
5303746210 5262479222 5346682277 5299354906 5290045662 5350552810 5343191051 5268759163 5299354906 5340227887 5299354906 5253956732 5289945955 5230918240 5287812187 5299354906 5299354906 5273800386 5299354906 5299354906 5353471727 5283662384 5230330060 5319166005 5338060400 5304825609 5268929476 526...
result:
ok 9541 numbers
Test #4:
score: 0
Accepted
time: 483ms
memory: 118952kb
input:
3 500000 891 806445768 895003544 461699845 184479965 853541910 593542573 667984604 465354540 303586741 243665567 285056069 294245042 675066412 456713460 215929340 756894934 773828574 317143965 451366539 891390118 436168373 633752416 78781758 298770626 35280548 226923750 96421159 523108871 265102517 ...
output:
5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 5202946193 520...
result:
ok 9000 numbers
Test #5:
score: 0
Accepted
time: 883ms
memory: 119000kb
input:
4 500000 3000 303543765 129078653 192039183 226458565 208138322 436645868 210834986 135457074 162914826 137413668 192916902 146302909 434058637 370665799 433071720 460608259 413021067 44008462 416238964 258228162 317315155 28299542 422136622 102236305 489978791 223662501 132197157 47793593 265792210...
output:
50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 50490529 504...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 441ms
memory: 118996kb
input:
3 500000 895 688 1201 2221 3857 4357 4465 8482 8585 9839 11049 11429 11462 11467 12642 13620 14171 14220 14419 15332 17522 18107 18753 18851 18863 18915 20273 20374 20482 22320 22934 24333 25223 25947 26879 27015 27794 27850 29892 31082 31103 35023 35611 36010 36365 36452 36708 36830 37302 39844 427...
output:
102387246746 102601622426 102404770741 102607362161 102607362161 102607362161 102475496180 102558851848 102607403181 102607362161 102427271560 102593532165 102583224195 102607362161 102607362161 102607362161 102605413877 102607362161 102607362161 102607362161 102607362161 102607362161 102607362161 1...
result:
ok 9000 numbers
Test #7:
score: 0
Accepted
time: 885ms
memory: 119148kb
input:
4 500000 3000 807 3313 3431 3532 3653 4229 4574 5708 6325 7571 8354 11026 11363 17596 18919 20930 23420 25860 26462 27514 29428 30001 31416 33806 35417 35902 36640 37602 38082 40496 43170 44783 45474 46146 48538 49134 49711 55502 56776 56805 57172 62132 62994 66887 69086 70397 70840 71041 74735 7581...
output:
53400340472 53262820133 53408913719 53408913719 53139987488 53408913719 53391409768 53408913719 53297244457 53408913719 53408913719 53408913719 53408913719 53408913719 53408913719 53408913719 53370502963 53408913719 53408913719 53408913719 53408913719 53408913719 53183451361 53408913719 53250342681 ...
result:
ok 10000 numbers
Test #8:
score: 0
Accepted
time: 475ms
memory: 118976kb
input:
3 500000 898 72235410 72235201 72234995 72234626 72234618 72234521 72234278 72234246 72234049 72233851 72233816 72233538 72233508 72233443 72233401 72233339 72233290 72233253 72233209 72233115 72233082 72233035 72232958 72232727 72232634 72232375 72232328 72232273 72232147 72231963 72231949 72231774...
output:
20193388372 20193082246 20193388372 20193388372 20137454774 20188193632 20193388372 20142612908 20193388372 20193388372 20193388372 20193388372 20193388372 20193388372 20138539830 20187126013 20193388372 20193388372 20193388372 20193388372 20186094266 20193388372 20193388372 20193388372 20193388372 ...
result:
ok 9000 numbers
Test #9:
score: 0
Accepted
time: 890ms
memory: 118996kb
input:
4 500000 3000 940751349 940750988 940750901 940750476 940748407 940746205 940745797 940741835 940740148 940736196 940735197 940734866 940730194 940729360 940725799 940725665 940725655 940725053 940723831 940721542 940721363 940717981 940717755 940714833 940712714 940711645 940710684 940709233 940708...
output:
77887099213 77887099213 77887099213 77887099213 77887099213 77887099213 77887099213 77828029837 77887099213 77887099213 77671399735 77743075018 77549812395 77887099213 77887099213 77817237157 77887099213 77887099213 77887099213 77887099213 77887099213 77887099213 77887099213 77887099213 77887099213 ...
result:
ok 10000 numbers
Test #10:
score: 0
Accepted
time: 458ms
memory: 119060kb
input:
3 500000 197 249644882 249644882 249644882 210710900 249644882 249644882 249644882 249644882 249644882 249644882 249644882 249644882 249644882 249644882 249644882 245319185 249644882 249644882 249644882 78092123 249644882 249644882 249644882 249644882 249644882 249644882 249644882 249644882 24964488...
output:
131507955421 131507955421 131507955421 131507955421 131507955421 131509822232 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 131507955421 1...
result:
ok 9000 numbers
Test #11:
score: 0
Accepted
time: 872ms
memory: 118996kb
input:
4 500000 3000 831 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 161289 128794 161289 161289 106109 161289 161289 161289 161289 161289 161289 161289 161289 161289 190991 161289 161289 161289 16...
output:
197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826 197826...
result:
ok 10000 numbers
Test #12:
score: 0
Accepted
time: 656ms
memory: 119028kb
input:
4 498000 3000 999999994 999999999 999999994 999999991 999999995 999999996 999999990 999999991 999999998 999999998 999999993 999999999 999999995 999999994 999999990 999999996 999999991 999999999 999999992 999999993 999999991 999999994 999999994 999999995 999999993 999999996 999999999 999999992 999999...
output:
165000000490 165000000794 165000000989 164999999136 165000001051 164999998817 165000001132 164999998874 164999998746 164999999349 165000000359 165000001251 165000000882 164999999400 164999999628 164999998782 165000001164 165000001353 164999998477 164999999056 165000001286 165000000562 164999998745 1...
result:
ok 10000 numbers