0

https://www.hackerrank.com/challenges/gridland-metro/problem This is the link to the question in hacker rank.

#include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  int tot = n * m;
  vector<vector<int>> track;

  for (int i = 1; i <= n; i++) {
    track[i][0] = INT_MAX;
    track[i][1] = INT_MIN;
  }

  while (k--) {
    int r, c1, c2;
    scanf("%d%d%d", &r, &c1, &c2);

    if (track[r][0] > c1 && track[r][1] < c2) {
      if (track[r][0] == INT_MAX && track[r][1] == INT_MIN) {
        track[r][0] = c1;
        track[r][1] = c2;
        tot -= c2 - c1 + 1;
      } else {
        tot -= (track[r][0] - c1) + (c2 - track[r][1]);
        track[r][0] = c1;
        track[r][1] = c2;
      }
    } else if (track[r][0] <= c1 && track[r][1] >= c2) {
      tot -= 0;
      continue;
    } else if ((track[r][1] > c1 && track[r][0] < c1) && track[r][1] < c2) {
      c1 = track[r][1] + 1;
      tot -= c2 - c1 + 1;
    }
  }

  printf("%lld", tot);
}

This is my code for the question and I am getting segmentation fault in this. PLz tell me the right way of doing this program because I guess my code is brute force one if it was made correct

t.niese
  • 39,256
  • 9
  • 74
  • 101
Abhishek Bajaj
  • 21
  • 4
  • 7
    Your question is evidence why you can't learn C++ from random hackerrank or other online judge websites. `vector> track; for(int i=1;i<=n;i++) { track[i][0]=INT_MAX; track[i][1]=INT_MIN; }` -- Please look at that code. Vectors do not resize themselves. In short, hackerrank and other websites assume you know the language you're using thoroughly enough, and focus their questions on data structures, algorithms, and math tricks. – PaulMcKenzie May 24 '20 at 15:33
  • 4
    [Why should I not #include ?](https://stackoverflow.com/q/31816095/5910058) – Jesper Juhl May 24 '20 at 15:35
  • Slight correction to above: `vector`s DO resize themselves, but not if you use the `[]` operator. `[]` is build to mimic the behaviour of accessing a plain old array with `[]`: Extremely fast access with zero error checking or special features like resizing. [Consult `std::vector` documentation](https://en.cppreference.com/w/cpp/container/vector) for how to properly use a `vector`. – user4581301 May 24 '20 at 15:42
  • [See the documentation](https://en.cppreference.com/w/cpp/container/vector). Look at the **Modifiers** section and the [constructor](https://en.cppreference.com/w/cpp/container/vector/vector). You need to either construct your vector, giving it the size in the constructor argument, or modify it by calling one of the modifier functions at that link. – PaulMcKenzie May 24 '20 at 15:50

1 Answers1

0

This may help you, however you have to change your approach of thinking :

2 reasons of segmentation fault :

  1. As others have told , you have to first allocate memory/initialize the vector. It automatically does not know what size to take.
  2. In your question the value of n , m < = 10^9, if you allocated memory containing that many entries then it may amount to atleast (500 MB) which is very large.

1 possible reason for timeout :

  1. There is a for loop running from 1 to n which can be in worst case 10^9 times. This itself will timeout even if you somehow manage to allocate memory. Refer this for timeout issues.

Nevertheless for your brute force approach you may try this : 

#include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  int tot = n * m;
  vector<vector<int>> track(n+1);
  //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

  for (int i = 1; i <= n; i++) {
    track[i] = vector<int>(2);
    //^^^^^^^^^^^^^^^^^^^^^^^^^^^
    track[i][0] = INT_MAX;
    track[i][1] = INT_MIN;
  }

  while (k--) {
    int r, c1, c2;
    scanf("%d%d%d", &r, &c1, &c2);

    if (track[r][0] > c1 && track[r][1] < c2) {
      if (track[r][0] == INT_MAX && track[r][1] == INT_MIN) {
        track[r][0] = c1;
        track[r][1] = c2;
        tot -= c2 - c1 + 1;
      } else {
        tot -= (track[r][0] - c1) + (c2 - track[r][1]);
        track[r][0] = c1;
        track[r][1] = c2;
      }
    } else if (track[r][0] <= c1 && track[r][1] >= c2) {
      tot -= 0;
      continue;
    } else if ((track[r][1] > c1 && track[r][0] < c1) && track[r][1] < c2) {
      c1 = track[r][1] + 1;
      tot -= c2 - c1 + 1;
    }
  }

  printf("%lld", tot);
}
KL_KISNE_DEKHA_HAI
  • 649
  • 11
  • 26