QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#609879#5452. Tractor PathsDimash#43.75 354ms29432kbC++232.3kb2024-10-04 14:19:172024-10-04 14:19:19

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 14:19:19]
  • 评测
  • 测评结果:43.75
  • 用时:354ms
  • 内存:29432kb
  • [2024-10-04 14:19:17]
  • 提交

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...

result: