QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#425143 | #7522. Sequence Shift | pandapythoner | TL | 211ms | 12108kb | C++20 | 2.0kb | 2024-05-29 22:36:14 | 2024-05-29 22:36:16 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const ll inf = 1e18;
mt19937 rnd(234);
const ll mod = 1e9 + 7;
typedef complex<flt> base;
const flt pi = atan2(1, 0) * 2;
const int maxn = 1e6;
int n, q;
int a[maxn];
int b[maxn * 2];
int rs[maxn + 10];
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> n >> q;
for (int i = 0; i < n; i += 1) {
cin >> a[i];
}
for (int i = 0; i < n; i += 1) {
cin >> b[i];
}
for (int i = 0; i <= q; i += 1) {
rs[i] = 0;
}
vector<int> sa(n);
for (int i = 0; i < n; i += 1) {
sa[i] = i;
}
sort(all(sa), [&](int i, int j) {return a[i] > a[j];});
int last = 0;
int b_can_do = 4e8 / n;
int b_border = max(0.0, 1e9 - (1e9 / (n + q) * b_can_do));
int super_can_do = 4e8 / 1e4;
int super_border = max(0.0, 1e9 - (1e9 / (n + q) * super_can_do));
auto update = [&](int j) {
int l = max(0, j - q);
int r = min(j, n - 1);
int pos = b[j] / (1e9 / (n + q));
assert(0 <= pos and pos < n + q);
int aboba = (flt)(60) * (n + q) / (n + q - pos);
aboba = max(aboba, 60);
aboba = min(aboba, n - 1);
for (int x = 0; x <= aboba; x += 1) {
int k = sa[x];
if (l <= k and k <= r) {
rs[j - k] = max(rs[j - k], a[k] + b[j]);
}
}
};
for (int j = 0; j < n; j += 1) {
update(j);
}
for (int i = 0; i <= q; i += 1) {
last = rs[i];
cout << last << "\n";
if (i < q) {
int j = n + i;
cin >> b[j];
b[j] ^= last;
update(j);
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7920kb
input:
5 3 1 4 3 2 5 7 5 8 3 2 3 6 4
output:
11 13 16 25
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 7660kb
input:
1 0 103509429 823330096
output:
926839525
result:
ok single line: '926839525'
Test #3:
score: 0
Accepted
time: 0ms
memory: 7656kb
input:
1 1 576560149 691846236 1156187222
output:
1268406385 835582012
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 7888kb
input:
1 10 700282491 332230980 90825676 1630266999 644973380 262379760 2122877054 1851957134 1370195232 110993724 1319359505 1883523208
output:
1032513471 1654684398 759763732 888538827 1695749302 1163465539 1425605448 789576931 1397740634 1202288326 1638577353
result:
ok 11 lines
Test #5:
score: 0
Accepted
time: 37ms
memory: 12048kb
input:
1000 100000 438001359 929744877 710148392 323984311 727016267 323629255 495752276 309120511 312675195 717795522 937464489 624952229 444774478 829169766 707441777 609125148 25459976 849166512 716162953 882416779 189669312 135698832 632796131 592794700 569746403 231058028 389412868 824283503 801480367...
output:
1962871590 1986083253 1967509108 1973351244 1974354421 1956371849 1976394149 1995721753 1946870160 1984280254 1961237540 1955903880 1944520591 1937726835 1993563403 1927000559 1951483558 1979133252 1979156812 1941301401 1922284543 1980597785 1963663583 1946961524 1933606347 1953947075 1953071855 194...
result:
ok 100001 lines
Test #6:
score: 0
Accepted
time: 11ms
memory: 7776kb
input:
10000 10000 760845880 236665988 765352292 817854026 789863420 399953246 270535243 932350041 48814223 670950468 456660682 416165008 999681497 666880584 56581573 134567049 403285848 144814129 973325555 23519957 518449311 738687225 345716065 2309498 477743569 555951695 911860717 920761968 569179690 349...
output:
1990514380 1974843876 1992500750 1994731468 1983411218 1986646709 1979643361 1990060423 1988174297 1983373232 1995134632 1989936349 1993187026 1988927807 1971595730 1988272839 1990590966 1981928791 1987819156 1987483957 1979800700 1986611531 1973877196 1995735988 1985734454 1987573480 1988935268 199...
result:
ok 10001 lines
Test #7:
score: 0
Accepted
time: 59ms
memory: 12108kb
input:
10000 100000 682604470 430466819 955519058 186918998 587587373 201134122 473675328 586747694 132807628 255672373 504315038 137082392 753499284 586570202 133549919 570424589 87103369 2142325 895908281 852456682 239920694 443878018 717067433 437134318 39426086 82137124 698018668 518394430 430778732 56...
output:
1984544998 1988859370 1989789541 1976833784 1995823502 1972653611 1991119857 1993356707 1986981779 1995476314 1995610828 1993831190 1996638827 1986403811 1989382087 1993806832 1989374332 1994121941 1983565702 1985256743 1996937615 1982877527 1995705250 1986803258 1991586243 1985584711 1989505176 199...
result:
ok 100001 lines
Test #8:
score: 0
Accepted
time: 100ms
memory: 7704kb
input:
100000 1000 765888053 833515469 84953776 797547408 412620563 765574495 334638552 473705288 279331343 321129745 718689650 778307179 205668791 48820839 279108389 210915881 711034474 688831194 230042027 856832739 427928795 151766103 505848143 403162288 459045522 979683261 59438197 871004123 755234923 6...
output:
1998969019 1997756723 1990964658 1992180114 1991311226 1996318953 1999238402 1997012356 1996382741 1993901604 1990703168 1997121645 1996347278 1990978439 1993663588 1996287457 1998005763 1997236433 1994552013 1995785880 1997513392 1998761277 1994793469 1993807193 1997817922 1990146164 1997588498 199...
result:
ok 1001 lines
Test #9:
score: 0
Accepted
time: 123ms
memory: 8008kb
input:
100000 10000 155192094 32355226 10722958 680788712 355467230 837266625 393682487 504944520 573979360 618892727 168735423 928295170 158663199 129313725 187722419 800899194 169961946 297789942 3327780 993559861 568700692 901642218 989795879 846649116 947423253 851741191 365690710 469648703 903510759 7...
output:
1998324839 1998650520 1996715356 1996337565 1994069244 1994071960 1994680032 1995482692 1995353396 1996020788 1998370988 1994450866 1997311656 1992935357 1998022252 1998633241 1998507677 1997594278 1996419001 1997075873 1997413924 1995735160 1995881483 1995263027 1997718803 1998739520 1997494429 199...
result:
ok 10001 lines
Test #10:
score: 0
Accepted
time: 211ms
memory: 8060kb
input:
100000 100000 38413036 456923902 821971466 586909482 636298728 158178471 84422915 632002470 34405999 882453211 922025994 294603996 207311349 526030511 417456448 362917277 456078308 435018316 47342069 47738636 642863127 189926256 40263985 58857249 119358305 864464366 83617839 485428518 305918980 9423...
output:
1996429420 1996287202 1997245731 1997158288 1998410767 1992680343 1996866185 1991187990 1993994382 1993278697 1998519189 1996981873 1996505587 1999396980 1996368678 1994926892 1995154606 1996246700 1998278411 1995699098 1998553319 1996046134 1996078476 1994270984 1993675913 1998307200 1994292194 199...
result:
ok 100001 lines
Test #11:
score: -100
Time Limit Exceeded
input:
1000000 1000000 681721767 150525996 385619734 237403201 784389657 667934330 103476610 977301142 659915560 343444475 784049915 969172199 251161944 919517420 927740574 885570202 531822081 391391357 889183133 954725705 921897422 339841876 886216126 698710851 968534847 834323464 33830362 168121355 74737...
output:
1998411706 1999115826 1999454117 1998836657 1998794667 1998269776 1999755051 1999381591 1998357039 1998230113 1999809722 1999320829 1999229409 1999798765 1998535400 1998709328 1999265546 1997784237 1998664760 1999789557 1998603617 1999595456 1999705003 1998179238 1999135621 1998190124 1998561110 199...