Why is vector much slower than static array in my binary lifting implementation?
Difference between en7 and en8, changed 0 character(s)
I was solving the Planets Queries I problem in CSES (a standard binary lifting problem). ↵
↵
After getting a few TLE on one of the test cases, I finally got AC, but it took 1.00 seconds to pass that test case, which is way too close. ↵
On checking other submissions with exact same logic, and investigating a bit more, I changed vector\<vector\<int\>\> declaration in my code to static int array declaration, and my code, with everything being exact same, worked in 0.60 seconds. ↵
↵
Usually there shouldn't be such a drastic difference. While solving codeforces problem, I have observed that vectors and static array take the same time, and sometimes vectors are faster. ↵
↵
Can anyone explain the reason behind this? Thanks.↵
↵
Submission using vector\<vector\<int\>\> : https://cses.fi/paste/7d2b7a0b66df52a2ea28b6/ ↵
↵
Submission using static int array : https://cses.fi/paste/6d8b9ef1a192caa1ea28f1/

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English Argentum47 2025-11-20 11:43:07 3 Tiny change: 'ntation, I did vec' -> 'ntation, If I did vec'
en9 English Argentum47 2025-11-19 19:16:56 1017
en8 English Argentum47 2025-11-19 18:20:07 0 (published)
en7 English Argentum47 2025-11-19 18:19:40 2
en6 English Argentum47 2025-11-19 18:19:03 21 Tiny change: 'ged vector<vector<int>> declarat' -> 'ged vector\<vector\<int\>\> declarat'
en5 English Argentum47 2025-11-19 18:17:53 4 Tiny change: 'hanks.\n\nSubmissi' -> 'hanks.\n\n<int>\nSubmissi'
en4 English Argentum47 2025-11-19 18:15:49 14 Tiny change: 'econds. \nUsually ' -> 'econds. \n\nUsually '
en3 English Argentum47 2025-11-19 18:14:12 1 Tiny change: 'ea28b6/ \nSubmissi' -> 'ea28b6/ \n\nSubmissi'
en2 English Argentum47 2025-11-19 18:13:19 16
en1 English Argentum47 2025-11-19 18:12:48 986 Initial revision (saved to drafts)