11402 - Ahoy, Pirates!

[brianfry713]

Input:

Code: Select all

1
1
64
110000011101011110011110110010001
345
F 951 1793
S 43 491
S 36 1431
I 1529 2065
I 516 946
S 344 1395
S 440 745
F 609 1598
F 410 1438
S 484 1211
I 956 1141
E 909 1447
E 1547 1793
I 1244 1500
I 334 398
E 807 1356
I 3 1616
S 586 1167
I 226 493
E 978 1562
E 71 1209
F 980 1808
S 401 661
F 490 1969
I 191 2108
E 82 1547
I 1550 1564
E 89 1374
I 379 1857
F 703 2006
S 760 1167
F 863 1837
E 137 1329
S 1819 2097
I 1397 1880
I 1159 1962
F 1414 1729
E 676 1867
E 422 1060
S 746 1189
I 1475 1950
I 162 1675
S 1813 2006
I 288 1862
I 603 1147
E 258 1173
S 1179 2051
F 752 1806
I 413 818
S 518 1629
E 581 992
E 1218 1748
I 1113 1794
F 1057 1465
S 91 2068
E 942 1193
E 261 1707
S 1013 1838
I 534 1490
S 1764 2009
S 24 542
E 242 297
I 134 2036
S 1045 1848
S 1137 1200
E 31 1827
I 601 1802
S 1426 1528
E 2009 2063
I 1299 1779
E 106 1803
S 2081 2101
F 187 1051
E 1133 2036
I 569 1188
E 24 904
S 673 1569
F 883 1583
S 780 1522
I 840 2080
I 138 182
S 3 108
I 67 1159
I 119 180
S 813 1216
S 838 1403
F 1511 1556
S 1047 1464
S 521 788
S 63 1425
I 1117 1608
I 1611 1927
E 678 1742
E 1729 1925
S 655 1094
E 385 770
F 1853 2005
S 281 1421
E 97 1704
I 160 1796
I 1342 1983
I 197 1221
F 631 1900
I 176 1581
F 188 2078
E 569 959
I 700 2010
F 802 982
E 574 706
I 322 1067
F 258 869
E 104 455
E 1014 1087
I 1327 1618
S 1293 2100
I 1500 1862
I 1413 1760
F 515 1220
S 400 1221
E 240 1789
S 1109 1227
S 1213 2071
I 179 2089
E 1862 1894
S 1233 1850
E 760 1303
I 604 1310
E 448 1888
I 240 633
I 1456 2030
S 489 1145
E 1169 1957
F 1210 1768
I 554 992
E 177 731
F 90 1001
F 199 1376
E 198 712
E 1409 1647
S 93 753
E 955 1306
I 814 1151
F 807 1887
F 1092 1425
I 46 109
S 263 851
S 847 1639
S 1512 1837
F 1436 2017
E 650 1593
S 436 1314
S 1075 1315
I 1090 2005
F 134 2097
E 181 1069
F 283 1096
F 499 1944
E 1042 1408
I 121 1313
S 737 2027
F 1229 2042
S 192 557
E 149 160
F 198 699
E 615 1332
E 640 1615
E 66 992
E 936 1108
I 606 1293
I 1776 2094
S 315 2024
F 470 1467
E 694 1886
F 1284 1457
F 24 816
S 593 728
I 1466 1721
I 124 609
F 189 1215
I 943 1632
S 878 1259
E 678 1417
S 37 517
E 919 1801
E 569 2063
I 251 1226
S 182 644
F 180 768
F 1022 1415
S 606 1831
I 117 1548
E 492 853
I 891 1465
S 1021 1874
F 1825 2034
I 28 1023
I 210 741
S 132 455
E 197 1870
S 1413 1653
S 1524 1770
F 215 847
S 912 1680
E 653 1494
I 639 1765
I 557 1663
E 356 575
F 553 1237
I 620 814
S 115 1089
E 116 1703
F 502 627
E 1414 2056
I 215 796
I 249 513
E 1070 2107
E 1645 1882
I 835 1931
F 323 1519
S 561 649
S 516 677
E 105 1369
F 1377 2022
F 1523 1592
I 1613 1841
F 295 1901
I 704 1671
E 1470 1554
F 740 1941
E 478 889
S 1058 1152
F 1071 1163
E 1137 1557
E 612 1345
S 114 1993
F 473 1043
S 1178 1228
E 600 946
I 1404 1499
F 181 1523
I 1398 2109
E 357 1260
S 1844 1978
S 1211 1693
E 1022 1157
S 152 209
E 1233 1444
E 278 1880
E 1841 1969
S 1317 1951
E 299 1314
I 526 1817
E 258 339
F 62 1951
E 397 925
I 847 1135
I 320 1898
E 153 2015
I 74 620
S 629 2026
E 213 884
S 425 2031
E 322 388
F 281 384
I 781 1385
E 1535 1692
E 1542 1901
I 1445 1599
E 1640 2065
S 647 1411
F 386 1595
S 740 2085
E 425 1619
E 645 706
S 1685 2091
S 1514 1539
I 480 1367
S 919 1918
E 447 1396
F 1013 1858
S 197 544
F 353 1001
E 144 572
S 258 1217
S 755 855
E 50 282
E 827 1038
F 697 1456
S 45 1271
I 1059 1104
S 1648 1667
F 1676 2084
F 117 1676
I 54 375
E 1185 1194
S 248 1245
I 171 890
S 787 1691
E 914 1603
F 754 2083
S 1619 1892
F 1115 1247
E 876 1403
F 216 930
I 67 246
S 316 1195
I 378 1206
E 389 2057
F 1160 1548
S 254 1977
I 35 1805
I 1214 1253
I 570 673
F 274 786
S 250 1096
S 179 1420
E 557 1724
I 150 1010
I 59 332
E 1428 2100
F 383 1858
I 999 1021
F 859 1736
I 1509 2074
I 212 1041
E 577 1632
S 556 1308
E 1523 1742
F 760 1855
E 1171 1327
S 100 1618
I 591 1084
I 1170 1451
F 912 1827
F 1221 1954
F 483 1776
E 461 1039
F 733 1816
S 22 1494
I 462 773
F 937 955
S 1194 2021
I 384 1079
S 858 1310
E 32 150

AC output:

Code: Select all

Case 1:
Q1: 246
Q2: 981
Q3: 737
Q4: 148
Q5: 728
Q6: 361
Q7: 0
Q8: 408
Q9: 234
Q10: 0
Q11: 169
Q12: 342
Q13: 1045
Q14: 1182
Q15: 53
Q16: 132
Q17: 128
Q18: 305
Q19: 0
Q20: 103
Q21: 9
Q22: 137
Q23: 640
Q24: 9
Q25: 304
Q26: 279
Q27: 113
Q28: 268
Q29: 1029
Q30: 23
Q31: 104
Q32: 371
Q33: 765
Q34: 0
Q35: 134
Q36: 557
Q37: 145
Q38: 146
Q39: 139
Q40: 793
Q41: 326
Q42: 0
Q43: 0
Q44: 891
Q45: 91
Q46: 848
Q47: 136
Q48: 109
Q49: 416
Q50: 138
Q51: 810
Q52: 478
Q53: 30
Q54: 0
Q55: 0
Q56: 0
Q57: 507
Q58: 89
Q59: 162
Q60: 95
Q61: 619
Q62: 0
Q63: 0
Q64: 171
Q65: 29
Q66: 0
Q67: 4
Q68: 9
Q69: 605
Q70: 880
Q71: 26
Q72: 0
Q73: 449
Q74: 159
Q75: 634
Q76: 101
Q77: 699
Q78: 20
Q79: 860
Q80: 791
Q81: 274
Q82: 615
Q83: 513
Q84: 823
Q85: 994
Q86: 0
Q87: 853
Q88: 945
Q89: 828
Q90: 231

[darkstallion]

woah! that's really a long test case! How did you make that test case?

However I managed to know the bug in my code and I got AC, thanks to your test case, brianfry713!

[brianfry713]

I wrote a test case generator using rand()

[tamim1382csedu19]

Is it solvable using BIT? I am trying to solve it using fenwick tree. But its giving me TLE. Heres my code , http://ideone.com/krmc4n

[brianfry713]

From uhunt:
AKJ88> tamimcsedu19, Use segment tree and count the number of Buccaneer pirates in each range.

[tamim1382csedu19]

I have used lazy updates. Still getting TLE. Here's My code
http://ideone.com/EKNaRN

[tamim1382csedu19]

SomeOne please help.. I am Trying all day long but couldn't find a way to do >.... getting TLE after using segment tree with lazy updates too.. http://ideone.com/WDK1eu

[vaush]

Both of your versions, and i think a lot of others', are coded with the same mistake: you don't get the newline character between the number of repetitions of the binary string and the string itself. After getting the number of repetitions, use a double getline(cin, str), where str is the variable in which you want to record the binary string: the first time you get rid of the newline and the awful lot of spaces in between, and with the second one you get the actual string

[tamim1382csedu19]

But, I am getting TLE,, How I avoid that?

[Blackwizard]

Hi...

I used segment tree with lazy propagation to update for this problem.
But I'm getting WA!
Is there any tricky case?!

Here's my code: http://ideone.com/4NNbV5

Thanks for your help...

[vector9x]

Hi...

I used segment tree with lazy propagation to update for this problem.
But I'm getting WA!
Is there any tricky case?!

Here's my code: http://ideone.com/4NNbV5

Thanks for your help...

I think you need to interchange lines 45 and 46 as well as 60 and 61.
I mean, perform lazy_propagation after checking the interval, because lazy_propagation uses r and l

[AmirAz]

I used segment tree, O(n log n) building, and maximum O(2 log n) = O(log n) for each query or update. here is my code and i get TLE can you tell me what should I change?

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <algorithm>
#include <ctype.h>
#include <map>
#include <vector>
#include <stack>
#include <climits>
#include <functional>
#include <sstream>
#include <math.h>

using namespace std;
#define lli long long int
#define llu long long unsigned
#define ii pair<int, int>
#define vii vector<ii>
#define vi vector<int>
#define log2(n) log10(n) / log10(2)
#define getMid(a, b) floor(a + b) /2;
#define mii map<int,int>

class SegmentTree{

public:
int tree_len, *tree; bool *source; int size;
int build(int p, int s, int e){
if (s == e)
return tree[p] = (source[s]?1:0);
int mid = getMid(s, e);
return tree[p] = build((p<<1), s, mid) + build((p<<1) + 1, mid + 1, e);
}
SegmentTree(bool *ex , int n){
size = n;
int h = ceil(log2(size));
source = new bool [n];
for (int i = 0; i < n; i++)
source = ex;
tree_len = 2 * pow(2, h);
tree = new int[tree_len+1];
build(1, 0, size-1);
}

void update(int p, int s, int e, int idx, int diff){
if (s > idx || e < idx)
return;

if (s == e){
tree[p] += diff;
source[idx] = tree[p];
return;
}
int mid = getMid(s, e);
tree[p] += diff;
update((p<<1), s, mid, idx, diff);
update((p<<1) + 1, mid+ 1, e, idx, diff);
}

int getSum(int p, int s, int e, int i, int j){
if (s > j || e < i)
return 0;
if ((s == e) || ( s >= i && e <= j))
return tree[p];
int mid = getMid(s, e);
return getSum((p<<1), s, mid, i, j) + getSum((p<<1)+1, mid + 1, e, i, j);
}



};

int main(){
bool *source = new bool[1024000];
int T; cin >> T;

for (int tc = 1; tc <= T; tc++){
int m; cin >> m;
int size = 0;
for (int i = 0; i < m; i++)
{
int time; cin >> time;
string orig; cin >> orig;
for (int j = 0; j < time; j++)
for (int k = 0; k < orig.size(); k++)
source[size++] = (orig[k]=='1'?true:false);


}
SegmentTree st(source, size);
cout << "Case " << tc << ":\n";
int q; cin >> q; int god = 0;
for (int i = 0; i < q; i++){
int s, e; char a;
cin >> a >> s >> e;
if (a == 'F'){
for (int pos = s; pos <= e; pos++)
st.update(1, 0, size -1, pos, (st.source[pos] ? 0 : 1));
}
else if (a == 'E'){
for (int pos = s; pos <= e; pos++)
st.update(1, 0, size -1, pos, (st.source[pos] ? -1 : 0));
}
else if (a == 'I'){
for (int pos = s; pos <= e; pos++)
st.update(1, 0, size -1, pos, (st.source[pos] ? -1 : 1));
}
else if (a == 'S'){
cout << "Q" << ++god << ": " << st.getSum(1, 0, size -1, s, e) << "\n";
}
}


}
delete [] source;
}

[lbv]

I used segment tree, O(n log n) building, and maximum O(2 log n) = O(log n) for each query or update. here is my code and i get TLE can you tell me what should I change?

Using a segment tree does little good if you still do loops proportional to the size of the underlying array for every operation:

Code: Select all

for (int pos = s; pos <= e; pos++)
	st.update( ... );

There are ways to handle every operation in this problem with just one segment tree traversal. Try googling and you'll find a number of editorials on the web that discuss this in detail.

P.S. When posting source code, please use the code tags. Thanks.

[AmirAz]

Can you tell me what should I exactly search? I read the tutorial on geeksforgeeks.org and topcode.com but I found nothing useful

[lbv]

Can you tell me what should I exactly search? I read the tutorial on geeksforgeeks.org and topcode.com but I found nothing useful

I was referring to editorials about this specific problem, not about segment trees in general, but maybe I wasn't very clear, sorry.

Anyway, one such editorial that I know of is this one. You may find it helpful.