Roll_no_68's blog

Normal data structure vs Struct/Class
By Roll_no_68, history, 3 days ago, In English

So i had recently encountered with problem 380C - Sereja and Brackets I solved this problem using vector<vector<int>> of size (4*n X 3) which results in TLE. 299190493.

Basic segment tree was looking like this

vector<vector<int>> seg;
SegmentTree(int n) {
	seg.resize(4 * n, {0ll, 0ll, 0ll});
}

Then i just replace this part of code with

class node {
public:
	int full;
	int opn;
	int cls;
};
vector<node> seg;
SegmentTree(int n) {
	seg.resize(4 * n);
}

And this code got accepted.299237670

Does this means using class or struct can reduce time complexity although i know 1st code will occupy more memory as compared to 2nd but i am not sure about time. If anyone have any insights, could you please explain why this happened? Do they differ in terms of time complexity?

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Using array<int, 3> also results in AC. 299248827

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Means this issue arises only when using vectors

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Use tuple<int, int, int> or a struct as you did.

vector<int> has large overhead when you need to just a small constant number of elements, because it needs to allocate dynamic memory (via new) and do some extra bookkeeping (like the number of elements stored).

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay now i got it, also i think this question has very strict time limit otherwise this is not a very big problem (regarding time complexity).Right?

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The time complexity is same, but you should generally avoid it because using vector is just wasteful for this purpose.

      → Reply