QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#260112 | #1964. Stock Price Prediction | ucup-team288# | TL | 1261ms | 126736kb | C++20 | 4.3kb | 2023-11-21 20:13:22 | 2023-11-21 20:13:23 |
Judging History
answer
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i64 = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template <class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
constexpr int P = 1e9 + 9, B = 36784;
vector<int> pw;
int mul(int a, int b) {
return 1LL * a * b % P;
}
mt19937_64 rng(58);
using u64 = unsigned long long;
struct Info {
int sz = 1;
pair<int, int> val, first, last;
int h = 0;
Info(pair<int, int> p = {}) : val(p), first(p), last(p) {}
};
Info combine(Info a, Info b, int who) {
Info c;
c.sz = a.sz + b.sz;
c.val = who == 0 ? a.val : b.val;
c.first = a.first;
c.last = b.last;
i64 x = (b.first.second - a.last.second);
if (x < 0) { x += P; }
if (b.first.first == a.last.first) {
x = P - x;
}
c.h = (0LL + mul(a.h, pw[b.sz]) + mul(x, pw[b.sz - 1]) + b.h) % P;
return c;
}
struct Treap {
Treap *lc = nullptr, *rc = nullptr;
Info info;
u64 w = rng();
Treap(pair<int, int> p = {}) : info(p) {}
};
constexpr int N = 2e6;
Treap pool[N];
Treap* newNode(pair<int, int> p) {
static int n = 0;
return &(pool[n++] = Treap(p));
}
int size(Treap *t) { return t ? t->info.sz : 0; }
void pull(Treap *t) {
t->info = Info(t->info.val);
if (t->lc) {
t->info = combine(t->lc->info, t->info, 1);
}
if (t->rc) {
t->info = combine(t->info, t->rc->info, 0);
}
}
pair<Treap*, Treap*> split(Treap *t, int s) {
if (!t) { return {t, t}; }
Treap *a, *b;
if (s <= size(t->lc)) {
b = t;
tie(a, b->lc) = split(t->lc, s);
} else {
a = t;
tie(a->rc, b) = split(t->rc, s - size(t->lc) - 1);
}
pull(t);
return {a, b};
}
Treap* merge(Treap *a, Treap *b) {
if (!a) { return b; }
if (!b) { return a; }
if (a->w > b->w) {
a->rc = merge(a->rc, b);
pull(a);
return a;
} else {
b->lc = merge(a, b->lc);
pull(b);
return b;
}
}
int rnk(Treap *t, pair<int, int> val) {
int res = 0;
while (t) {
if (t->info.val <= val) {
res += size(t->lc) + 1;
t = t->rc;
} else {
t = t->lc;
}
}
return res;
}
void print(Treap *t) {
#ifdef KEV
auto rec = [&](auto rec, Treap *t) -> void {
if (!t) { return; }
rec(rec, t->lc);
cerr << '(' << t->info.val.first << ", " << t->info.val.second << ") ";
rec(rec, t->rc);
};
rec(rec, t);
cerr << '\n';
#endif
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
auto solve = [&]() {
int n, m;
cin >> n >> m;
pw.resize(m);
pw[0] = 1;
for (int i = 1; i < m; i++) {
pw[i] = mul(pw[i - 1], B);
}
if (n == 1) {
cout << m << '\n';
return;
}
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < m; i++) {
cin >> b[i];
}
i64 ha = 0;
{
Treap *t = nullptr;
for (int i = 0; i < n; i++) {
int r = rnk(t, pair(a[i], i));
auto [t1, t2] = split(t, r);
t = merge(t1, merge(newNode(pair(a[i], i)), t2));
}
ha = t->info.h;
print(t);
DE(ha);
}
Treap *t = nullptr;
for (int i = 0; i < n; i++) {
int r = rnk(t, pair(b[i], i));
auto [t1, t2] = split(t, r);
t = merge(t1, merge(newNode(pair(b[i], i)), t2));
DE(t->info.h);
}
print(t);
vector<int> ans;
if (ha == t->info.h) {
ans.push_back(0);
}
for (int i = n; i < m; i++) {
{
int r = rnk(t, pair(b[i - n], i - n));
auto [t1, t2] = split(t, r - 1);
auto [t3, t4] = split(t2, 1);
t = merge(t1, t4);
}
{
int r = rnk(t, pair(b[i], i));
auto [t1, t2] = split(t, r);
t = merge(t1, merge(newNode(pair(b[i], i)), t2));
}
if (ha == t->info.h) {
ans.push_back(i - n + 1);
}
print(t);
}
if (ans.empty()) {
cout << "0\n";
} else {
for (auto i : ans) {
cout << i + 1 << " \n"[i == ans.back()];
}
}
};
solve();
}
详细
Test #1:
score: 100
Accepted
time: 1082ms
memory: 126736kb
input:
10000 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 9...
output:
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 99 100 101 102 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...997 989998 989999 990000 990001'
Test #2:
score: 0
Accepted
time: 1260ms
memory: 120252kb
input:
10000 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 9...
output:
2 10002 20002 30002 40002 50002 60002 70002 80002 90002 100002 110002 120002 130002 140002 150002 160002 170002 180002 190002 200002 210002 220002 230002 240002 250002 260002 270002 280002 290002 300002 310002 320002 330002 340002 350002 360002 370002 380002 390002 400002 410002 420002 430002 440002...
result:
ok single line: '2 10002 20002 30002 40002 5000...002 950002 960002 970002 980002'
Test #3:
score: 0
Accepted
time: 185ms
memory: 121384kb
input:
3 1000000 23773 6970 7877 9961 10787 4539 31376 18151 23630 16391 12158 15840 13913 29761 19966 10776 11976 5869 30802 20826 11916 32327 14483 12010 14119 3033 30709 7610 13328 18508 31564 29408 31577 29055 2255 7240 16783 11990 6940 6054 1250 24533 17789 21935 13189 14573 11626 23945 4440 8853 1569...
output:
4 7 12 20 24 31 39 41 45 53 59 61 64 71 76 84 87 99 102 107 114 136 140 142 151 157 176 181 193 209 215 218 221 224 234 237 244 252 255 262 264 269 274 276 278 281 283 286 289 291 298 300 309 311 313 317 327 331 337 341 350 359 365 372 381 386 388 393 395 398 405 416 419 424 426 440 443 446 448 453 ...
result:
ok single line: '4 7 12 20 24 31 39 41 45 53 59...968 999974 999988 999994 999997'
Test #4:
score: 0
Accepted
time: 231ms
memory: 120908kb
input:
4 1000000 23802 5402 4815 29922 5314 7111 26620 24573 8394 26595 10827 16236 16555 14838 23087 2979 23962 7856 14510 3172 16351 7815 18544 9605 14474 4258 25878 24819 4961 5366 25805 23031 25884 31151 30754 28088 2517 4049 15384 21762 26554 13087 12919 2885 18949 2364 5224 9953 26670 15376 13119 169...
output:
38 46 55 67 93 98 103 148 198 206 218 239 278 305 319 341 351 380 423 433 460 463 472 496 503 512 518 527 530 574 589 598 628 643 652 667 671 751 765 771 790 808 824 841 845 859 869 906 946 979 987 1055 1072 1079 1086 1119 1132 1150 1166 1207 1239 1246 1252 1270 1282 1294 1359 1377 1381 1448 1501 15...
result:
ok single line: '38 46 55 67 93 98 103 148 198 ...772 999848 999908 999924 999958'
Test #5:
score: 0
Accepted
time: 257ms
memory: 120632kb
input:
5 1000000 23828 25853 16656 25821 22294 5757 18752 1155 9415 10178 9644 16589 29826 16137 4017 10612 9130 24186 29156 27529 9371 591 7591 186 225 27192 32506 25553 19369 4606 17044 28285 6260 7527 8755 17493 18963 15195 19248 28442 19919 17476 4950 4156 5864 6075 28660 19360 28225 32096 25393 20385 ...
output:
47 279 396 582 753 1076 1274 1401 1473 1543 1554 1665 1694 1774 1808 1983 2016 2088 2380 2554 2601 2760 2855 2897 3185 3210 3243 3385 3398 3447 3460 3789 3832 4090 4287 4420 4586 4620 4652 4715 4864 4876 5104 5163 5172 5177 5227 5446 5456 5475 5531 5543 5965 6409 7025 7177 7336 7589 7917 7978 8082 8...
result:
ok single line: '47 279 396 582 753 1076 1274 1...472 999607 999611 999672 999992'
Test #6:
score: 0
Accepted
time: 413ms
memory: 120372kb
input:
6 1000000 6109 28893 25285 520 16958 28875 31753 10319 16748 17536 6002 29630 25182 17187 13657 4568 20707 3163 19864 22175 7745 1126 11084 14669 6940 22117 13785 2373 2202 28922 19246 28489 25797 12565 3914 3821 22065 12043 21758 23628 31454 25065 1013 31225 7775 3335 8179 13113 6972 11232 21850 26...
output:
654 1240 1843 3023 3895 4380 4673 4751 5408 6412 6433 6669 7453 8072 8105 8712 9138 9988 11098 13149 14429 15249 17927 20310 21141 21171 21661 22107 22199 23414 24278 25489 26687 26901 27522 27780 28236 28752 28949 30412 30582 30634 30873 30938 31433 31637 32916 33609 33633 33743 34060 34665 35411 3...
result:
ok single line: '654 1240 1843 3023 3895 4380 4...512 996748 996889 998321 998528'
Test #7:
score: 0
Accepted
time: 381ms
memory: 120400kb
input:
7 1000000 23881 1220 7571 17618 23488 3049 3015 19855 11456 10113 7277 17293 23600 18734 31411 25877 12234 24077 25680 10708 28180 18910 18452 14115 4497 7525 12995 27020 15416 3087 32291 6025 32549 25817 30292 29070 19087 4718 26976 9034 6650 26255 21779 6699 12461 13496 9997 5408 31335 1 17173 249...
output:
1045 24944 28526 34260 39340 63308 69495 76724 81366 84878 86508 88193 89200 101564 113297 114228 123656 130070 130507 135773 149335 150468 162366 163333 165920 171929 184547 185512 189479 190007 193518 196923 199979 209159 220079 228435 240812 252945 258484 259629 264432 270954 271042 280078 283865...
result:
ok single line: '1045 24944 28526 34260 39340 6...222 982250 984828 985286 996439'
Test #8:
score: 0
Accepted
time: 1261ms
memory: 120304kb
input:
10000 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 9...
output:
5001 15001 25001 35001 45001 55001 65001 75001 85001 95001 105001 115001 125001 135001 145001 155001 165001 175001 185001 195001 205001 215001 225001 235001 245001 255001 265001 275001 285001 295001 305001 315001 325001 335001 345001 355001 365001 375001 385001 395001 405001 415001 425001 435001 445...
result:
ok single line: '5001 15001 25001 35001 45001 5...001 955001 965001 975001 985001'
Test #9:
score: 0
Accepted
time: 1107ms
memory: 124976kb
input:
10000 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 9...
output:
32761 32762 32763 32764 32765 32766 32767 32768 32769 32770 32771 32772 32773 32774 32775 32776 32777 32778 32779 32780 32781 32782 32783 32784 32785 32786 32787 32788 32789 32790 32791 32792 32793 32794 32795 32796 32797 32798 32799 32800 32801 32802 32803 32804 32805 32806 32807 32808 32809 32810 ...
result:
ok single line: '32761 32762 32763 32764 32765 ...997 989998 989999 990000 990001'
Test #10:
score: 0
Accepted
time: 1090ms
memory: 126612kb
input:
10000 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 9...
output:
32766 32767 32768 32769 32770 32771 32772 32773 32774 32775 32776 32777 32778 32779 32780 32781 32782 32783 32784 32785 32786 32787 32788 32789 32790 32791 32792 32793 32794 32795 32796 32797 32798 32799 32800 32801 32802 32803 32804 32805 32806 32807 32808 32809 32810 32811 32812 32813 32814 32815 ...
result:
ok single line: '32766 32767 32768 32769 32770 ...997 989998 989999 990000 990001'
Test #11:
score: 0
Accepted
time: 1105ms
memory: 126600kb
input:
10000 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 9...
output:
32767 32768 32769 32770 32771 32772 32773 32774 32775 32776 32777 32778 32779 32780 32781 32782 32783 32784 32785 32786 32787 32788 32789 32790 32791 32792 32793 32794 32795 32796 32797 32798 32799 32800 32801 32802 32803 32804 32805 32806 32807 32808 32809 32810 32811 32812 32813 32814 32815 32816 ...
result:
ok single line: '32767 32768 32769 32770 32771 ...997 989998 989999 990000 990001'
Test #12:
score: 0
Accepted
time: 871ms
memory: 125040kb
input:
10000 1000000 10001 10000 9999 9998 9997 9996 9995 9994 9993 9992 9991 9990 9989 9988 9987 9986 9985 9984 9983 9982 9981 9980 9979 9978 9977 9976 9975 9974 9973 9972 9971 9970 9969 9968 9967 9966 9965 9964 9963 9962 9961 9960 9959 9958 9957 9956 9955 9954 9953 9952 9951 9950 9949 9948 9947 9946 9945...
output:
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 99 100 101 102 ...
result:
ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...997 989998 989999 990000 990001'
Test #13:
score: 0
Accepted
time: 1098ms
memory: 126384kb
input:
10000 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 9...
output:
32767 32768 32769 32770 32771 32772 32773 32774 32775 32776 32777 32778 32779 32780 32781 32782 32783 32784 32785 32786 32787 32788 32789 32790 32791 32792 32793 32794 32795 32796 32797 32798 32799 32800 32801 32802 32803 32804 32805 32806 32807 32808 32809 32810 32811 32812 32813 32814 32815 32816 ...
result:
ok single line: '32767 32768 32769 32770 32771 ...997 989998 989999 990000 990001'
Test #14:
score: -100
Time Limit Exceeded
input:
10000 1000000 14 78 68 23 98 100 30 89 54 90 99 89 99 46 70 24 72 93 24 27 1 51 3 28 52 50 78 70 90 28 29 92 11 9 63 99 3 52 18 47 54 20 43 51 31 7 43 39 94 10 17 41 68 95 53 43 58 47 72 28 100 38 73 97 3 53 83 90 85 71 8 81 13 59 58 90 65 40 60 31 34 93 23 66 35 63 86 17 78 12 2 30 48 74 18 79 30 8...