QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#609879 | #5452. Tractor Paths | Dimash# | 43.75 | 354ms | 29432kb | C++23 | 2.3kb | 2024-10-04 14:19:17 | 2024-10-04 14:19:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 12, MOD = (int)1e9 + 7;
int n, q, d[N], up[N][19], l = 19;
string s;
pair<int, int> t[N * 4];
void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
if(tl == tr) {
t[v].first = val;
t[v].second = tl;
} else {
int tm = (tl + tr) >> 1;
if(pos <= tm) upd(pos, val, v + v, tl, tm);
else upd(pos, val, v + v + 1, tm + 1, tr);
t[v] = max(t[v + v], t[v + v + 1]);
}
}
pair<int, int> get(int l, int r, int v = 1, int tl = 1, int tr = n) {
if(l > r || tl > r || l > tr) return make_pair(0, 0);
if(tl >= l && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return max(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}
int dist(int v, int u) {
if(v == u) return 0;
int ret = 1;
for(int i = l - 1; i >= 0;i--) {
if(up[v][i] < u) {
ret += (1 << i);
v = up[v][i];
}
}
return ret;
}
void prec() {
int it = 1, col = 0;
for(int i = 1; i <= n + n; i++) {
char x;
cin >> x;
if(x == 'R') {
col--;
d[it++] = col;
} else {
col++;
}
}
upd(n, n);
for(int i = 0; i < l; i++) {
up[n][i] = n;
}
for(int i = n - 1; i >= 1;i--) {
int j = get(i + 1, i + d[i]).second;
up[i][0] = j;
for(int k = 1; k < 19; k++) {
up[i][k] = up[up[i][k - 1]][k - 1];
}
upd(i, i + d[i]);
}
}
vector<int> sp;
void test() {
cin >> n >> q;
prec();
for(int i = 1; i <= n; i++) {
char x;
cin >> x;
if(x == '1') {
sp.push_back(i);
}
}
while(q--) {
int a, b;
cin >> a >> b;
int res = dist(a, b), c =0 ;
for(int i:sp) {
// cout << i << ' ';
if(i >= a && i <= b) {
if(dist(a, i) + dist(i, b) == res) {
c += 1;
}
}
}
cout << res << ' ' << c << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
return 0;
}
詳細信息
Pretests
Final Tests
Test #1:
score: 6.25
Accepted
time: 1ms
memory: 7656kb
input:
8 10 LLLLRLLLLRRRRRRR 11011010 1 2 1 3 1 4 1 5 1 6 1 7 1 8 2 3 2 4 2 5
output:
1 2 1 1 1 2 2 4 2 3 2 4 2 3 1 1 1 2 1 2
result:
ok 20 numbers
Test #2:
score: 6.25
Accepted
time: 354ms
memory: 7872kb
input:
5000 5000 LLRLRLRLRLRLRLRLLLRLRRLLRRRLRLLLRRRLRLLLRRRLLRRLRLRLLRRLRLLRRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLLRLRRLRLRLLRRLRLRLRLRLRLRLRLLRRLRLRLRLLRLRLRLLRRRLRLRLRLRLRLRLRLRLLLLRRRLRLRRLRLRLRLRLLRLLRRRLRLRLRLRLLRLRRLRLRLRLRLRLLLRRRLRLLRRLLRRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLLRLRRLRLRLRLRLRLRLRLRLLR...
output:
1999 1394 631 344 559 293 646 342 713 397 1951 1292 134 296 1290 839 1254 1027 1330 1112 687 356 33 91 2 5 571 1010 1057 578 1786 1186 208 414 2044 1447 953 829 1269 912 820 435 1499 919 1689 1247 69 183 35 117 448 597 1665 1225 627 348 732 415 163 339 123 197 681 709 1673 881 689 747 29 98 1801 134...
result:
ok 10000 numbers
Test #3:
score: 6.25
Accepted
time: 338ms
memory: 7808kb
input:
5000 5000 LLRLRLRLRLLLLLRRRRLRRLRLLRLRRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLLRRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLLRRLRLRLRLRLLRRLRLRLRLLRRLRLLRRLRLRLRLLRRLRLLRLLLLRRRLRRRLRLRLLRRLRLLLRLRRRLRLRLRLLRRLRLRLRLRLRLLRRLRLLRRLLRRLRLRLRLLLRRRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLLRRLRLLRLLRLRRLRRLRLRLRLLRRLRLRLRLRLRL...
output:
186 91 73 243 68 116 4 18 170 389 1 0 1297 1191 1426 943 469 241 1789 1130 938 817 4 21 1316 690 615 539 555 285 1480 909 1092 657 572 711 115 55 2108 1351 107 601 1949 1302 533 496 4 51 1911 1034 1695 1015 218 102 603 403 1895 1531 703 565 302 484 515 253 751 396 1725 939 870 456 896 446 1418 732 8...
result:
ok 10000 numbers
Test #4:
score: 6.25
Accepted
time: 294ms
memory: 29432kb
input:
200000 200000 LLLRRLRLRLRLRLRLRLRLRLRLLRLRRLRLLRRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLLRRLRLRLLRRLRLLRRLRLRLLRLRRLRLRLRLRLRLRLLRRLRLRLLRLRLRRLRLRLLRRLRLLRRLRLLRRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLLRRLRLRLRLLRRLLRRLRLRLLRRLLRRLRLRLRLRLRLRLRLRLRLRLLRRLLR...
output:
16484 1 655 0 1517 0 11032 1 17293 4 30870 4 33999 3 74780 6 1850 0 29599 2 71012 6 266 1 14695 3 1648 1 82 0 56064 5 1364 0 4 0 67268 6 10 0 29492 4 47 0 4052 2 20545 3 1439 0 67845 6 21604 1 21288 3 29672 4 57680 4 41159 5 41529 6 15172 3 87 0 42937 5 30017 1 28295 4 33 0 26750 4 43539 5 43553 5 3...
result:
ok 400000 numbers
Test #5:
score: 6.25
Accepted
time: 289ms
memory: 26156kb
input:
200000 200000 LLRLRLRLLRLRRLRLRLRLLRRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLLRLLRRLRRLRLRLRLLRRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLRLRLRLRLLRRLRLRLRLRLLRRLRLRLRLRLRLLRRLRLLLRLRRRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLLRRLLRRLLRLRLRRLLRLLLRRRRLRLRLRLRLLRRLLRLRRLRLRLRLRLRLLLRRRLRLRLRLRLRLRLRLLLRRLLLRRRRL...
output:
26131 5 20974 5 1273 2 1512 3 19550 2 163 0 32871 1 69437 5 73141 6 22 0 40408 2 59158 4 3843 0 28987 7 1280 2 43180 5 1685 4 22520 5 80845 7 21239 1 31403 3 1468 2 43505 1 69232 3 41 1 47329 2 389 2 65752 7 5471 1 309 1 24754 7 1794 4 33241 1 7709 4 45311 2 38478 1 12876 0 50626 7 575 0 730 2 20 0 ...
result:
ok 400000 numbers
Test #6:
score: 6.25
Accepted
time: 285ms
memory: 29280kb
input:
200000 200000 LLLRRLRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLLRRRLRLRLLLRRRLRLLRLLLRRRLRRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLLRRLLLRRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLLRRLRLRLRLRLRLLRRLRLLRRLRLRLRLRLLRRLRLLRRLLRRLRLRLRLRLRLLLRRLRLRRLRLRLLR...
output:
48136 4 21402 7 41513 4 131 6 15137 0 14 0 30997 2 144 1 15998 0 67175 7 26 1 179 1 20 0 73265 10 39492 2 74604 4 4124 0 15777 2 45843 9 43185 3 66571 6 12661 0 38966 2 19994 1 41 0 18 1 75 1 64372 10 143 5 23 0 38583 2 52285 4 2 0 22974 3 7064 0 43522 4 121 3 59010 4 23787 8 35 3 69 2 45678 5 8943 ...
result:
ok 400000 numbers
Test #7:
score: 6.25
Accepted
time: 226ms
memory: 26512kb
input:
200000 200000 LLLRRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLLLRRRLRLRLLRRLLRRLLRRLRLLLRRRLRLRLRLRLRLRLRLRLRLRLRLLRLLRRLRRLRLLLRRRLRLRLRLRLLRRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLLRRLRLRLLLRLLRLRRRRLRLRLRLRLRLRLLRLLRRRLRLRLRLRLRLRLRLLRRLLLRRRLLRRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLLRRLRLLLRRRLRLRL...
output:
31339 1 7836 0 55074 1 21182 0 15631 0 721 3 51516 1 15481 1 40668 0 67728 1 30161 1 36547 0 178 1 9 0 68926 1 217 1 10052 0 3929 6 41507 0 63304 2 18966 0 20636 1 8210 0 726 0 65546 5 13261 2 23103 0 812 3 249 3 31587 4 47501 1 162 1 53257 2 114 1 13496 0 26613 0 33769 1 95 0 44876 1 44295 1 41811 ...
result:
ok 400000 numbers
Test #8:
score: 0
Time Limit Exceeded
input:
200000 200000 LLRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLLRRLRLRLRLLLLRLRRRLRRLRLRLRLLLLRRLRRRLLRRLLRRLRLRLRLRLRLRLLRLRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLLRLRRLRLRLRLRLLRLRLRRLRLLLRRRLRLRLRLRLRLRLRLLRRLRLLLRRLRLRRLRLRLLRRLRLLRRLLRRLRLRLRLRLRLRLLLRRRLLRRLLRRLRLRLRLRLRLRLRLRLRLRLLR...
output:
130 1128 15348 35056 28389 27051 26249 13714 30777 16127 94 6426 181 5084 72963 64060 117 1645 61711 38543 12236 11005 39712 20861 35 618 40298 37659 59600 35144 53308 54495 1292 15667 70240 53042 719 14390 4513 2870 52930 50544 78509 47453 106 5387 20154 27364 5677 15194 351 2323 1922 27429 15801 2...
result:
Test #9:
score: 0
Time Limit Exceeded
input:
200000 200000 LLLRRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLLRRLRLRLLRRLLRLRRLLLRRLRRLRLRLLRRLRLRLRLRLRLLRLRRLLRLRRLRLLRRLRLRLRLRLRLRLRLRLLLRRLRRLRLRLRLLLLRRRRLRLRLRLRLRLRLRLRLLRRLLRRLRLLRRLRLLLRRRLLRRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLLRRLRLRLLLRRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRLRRLLLRRRLRLRLLRRLRLRLRLRL...
output:
32610 29140 4145 2219 35988 29465 15767 8266 33276 17463 4219 2259 75369 41996 41492 21684 285 3057 25 219 19484 12432 262 1644 8498 18370 77876 51589 17401 9082 36834 22247 65 857 34952 27909 84 672 25829 13543 19738 10308 52191 36147 68175 44357 692 8760 20721 10856 397 6799 1818 12024 68510 46283...
result:
Test #10:
score: 0
Time Limit Exceeded
input:
200000 200000 LLRLLRRLRLLRRLRLLRRLRLLRRLRLLRRLRLRLRLLRRLRLRLRLRLRLLRLRRLRLLRRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLLRRLRLRLRLRLLLRLRLRLRRRLRLRLRLRLRLRLLRRLRLLRLRLRRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLLRLRRLRLRLRLRLRLRLLLRLRRRLRLRLRL...
output:
49378 57487 11210 5793 49079 54220 78290 49976 41 2844 62458 63721 45489 37578 8690 4500 4 112 54483 61077 76025 43585 39891 25594 237 14195 33146 20451 534 27844 339 20532 62573 52049 218 10771 14838 7730 17084 8895 7 334 25689 13485 36 1496 8071 4145 5862 33688 44387 23305 834 389 994 2688 47013 5...
result:
Test #11:
score: 0
Time Limit Exceeded
input:
200000 200000 LLRLRLLRRLRLRLLRRLRLLLRRLRLRRLRLRLRLRLRLRLRLRLLRLRLLRLRRLRRLRLRLRLRLRLLRRLLRRLRLRLRLLRRLLRLRRLRLRLRLRLRLRLRLLRRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLLRRLRLLRRLLRRLRLRLRLRLRLRLRLLRRLLRRLRLLRRLRLLRRLLRLRRLRLRLLLLRRRRLRLRLRLLLRRRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLLRRL...
output:
3446 21559 52081 38682 5 720 13168 12432 2149 1162 58 5945 22969 14910 302 17949 14457 7646 10020 7959 10220 5326 275 1619 33373 17441 8196 19884 37956 35381 13755 7262 25808 37741 12436 6564 4520 11163 43989 37799 666 27731 66624 42205 6869 3658 68874 51048 9225 15517 65715 47851 34016 36113 45072 ...
result:
Test #12:
score: 0
Time Limit Exceeded
input:
200000 200000 LLRLRLRLRLRLRLRLRLRLLRRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLLRLRRLRLRLRLRLRLRLLRRLRLRLRLLRRLRLLRRLLRRLRLLRRLRLRLRLRLRLRLRLRLLLRLRRRLRLRLRLRLLRLRRLLRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLLRLRRLRLLLRRRLRLRLRLRLRLRLLRRLLRLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLLRLRRRLRLLRRL...
output:
8341 4320 17304 8989 50324 35657 60725 31695 13661 10447 39520 49279 22480 20086 48811 42283 86 3672 7 217 285 28234 341 23951 217 20797 11814 6191 29 2838 42930 22412 4834 10116 48869 54136 70120 53084 64176 51504 155 23597 64718 51252 20594 10752 244 5879 3197 4295 26941 14057 55596 33791 42074 29...
result:
Test #13:
score: 0
Time Limit Exceeded
input:
200000 200000 LLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLLRRLRLRLRLRLRLLRRLRLLRLRRLRLRLRLRLRLLRRLLRLRRLRLRLLRRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLLRRRLLLRRRLRLRLRLLRLRRLRLRLRLRLRLRLLLRRRLRLLLRRRLRLLRRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLLRRLRLLLLLRRRRRLRLRLRLLRRLRLRLRLLRLRRLLLRRRLRLRLLRRLRL...
output:
2938 16907 2257 14763 28652 21985 78285 45096 2805 17151 35559 18762 70624 37153 94 2030 1412 16668 30527 27894 70850 55982 20 3369 23909 12478 181 801 3552 1817 58999 49357 21608 11277 1273 16489 20951 10958 19372 10162 6513 3451 8526 4490 60167 32474 6990 17495 880 4573 1230 7263 19950 33862 67659...
result:
Test #14:
score: 0
Time Limit Exceeded
input:
200000 200000 LLLRRLRLRLRLRLRLRLRLRLRLRLLLRRRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLLRRLRLRLRLLLRRRLRLLRRLLRRLLLRRRLRLRLLLLLRRRRRLRLRLRLRLLRLRRLRLLLRRRLLRLRRLRLRLRLRLLRLLRRRLRLLRRLRLLLRRRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLLRRLLLRLRRRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRLRLRRLLRLRRLLRRLRLRL...
output:
33415 17529 16839 31998 58006 44787 1653 11425 74712 60831 75580 57057 10240 5377 1022 6861 51487 33032 65566 56837 35513 38136 26064 25118 25843 16180 5131 14445 15371 8032 64125 33700 1708 13815 69260 49583 1071 9011 130 4389 2574 18746 21988 11463 279 1157 10624 5726 1402 10863 18687 9741 2210 17...
result:
Test #15:
score: 0
Time Limit Exceeded
input:
200000 200000 LLRLRLLRRLRLRLRLRLRLRLLRRLRLLRRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLLLRRRLRLRLRLRLRLRLRLRLRLLLRLRRRLRLRLRLRLRLLRRLLLLRLRRLRRRLRLRLLLRRLRRLRLRLRLRLRLRLRLRLLLLRRLLRRRRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLLLRRRLLRRLRLRLRLLLRRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRL...
output:
67484 35566 33071 17330 53695 37821 20598 10903 32384 16989 57205 35486 10800 5703 12056 6312 189 10065 47415 38766 49108 26235 195 13630 37344 20290 7354 5267 115 3988 62047 40541 5 871 14 2187 53696 28238 22297 20833 72528 38823 18864 25063 13171 7002 47426 34944 32419 17107 52712 33503 2004 1032 ...
result:
Test #16:
score: 0
Time Limit Exceeded
input:
200000 200000 LLRLRLLRRLRLRLRLRLRLRLLRRLRLRLLRRLRLRLLRRLRLLRRLRLLRRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLLRLRRLLLRRRLRLRLRLLLRRRLRLRLRLLLRRRLRLLRRLLLRLRLLRRRRLRLRLLRRLLRRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLLRRLRLRLRLRLRLRLRLRLRLRLLRRLRLLRRLRLLRRLRLRLRLRLRLRLRLRL...
output:
44477 23219 26913 22178 26243 18783 45 18824 49412 25800 30778 16132 27222 14237 20078 25981 87 25279 51 19096 66971 51791 106 25912 80 20601 76632 46015 4 685 34858 28480 61 2611 65937 57944 21912 11450 4 847 25 8427 76032 52138 17011 13112 78954 41871 11493 21917 40 12872 12863 13065 64799 33914 7...