electro177's blog

confusion in using iterator in vector
By electro177, history, 3 years ago, In English

Using set implementation it is working.but using vector the code gives some mingw error which i cannot understand.can anyone know what to do in order to make it work in vectors

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 2e5;
int n;
ar<int, 3> a[mxN];

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i][1] >> a[i][0] >> a[i][2];
  }
  sort(a, a + n);
  set<ar<ll, 2>> dp;
  dp.insert({0, 0});
  ll ldp = 0;
  for (int i = 0; i < n; ++i) {
    auto it = dp.lower_bound({a[i][1]});
    --it;
    ldp = max(ldp, (*it)[1] + a[i][2]);
    dp.insert({a[i][0], ldp});
  }
  cout << ldp;
}



#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 2e5;
int n;
ar<int, 3> a[mxN];

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i][1] >> a[i][0] >> a[i][2];
  }
  sort(a, a + n);
  vector<ar<ll, 2>> dp;
  dp.push_back({0, 0});
  ll ldp = 0;
  for (int i = 0; i < n; ++i) {
    auto it = lower_bound(dp.begin(), dp.end(), a[i][1]) ;
    --it;
    ldp = max(ldp, (*it)[1] + a[i][2]);
    dp.push_back({a[i][0], ldp});
  }
  cout << ldp;
}
  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Ok, so i've looked at this code for a while now and believe that now i understand what's going on

First, you're trying to compare stuff of different types, but the difference is that in the first scenario you used auto it = dp.lower_bound({a[i][1]});, and the {a[i][1]} part parses this data from int to an array, which is what it uses to compare to the items in the set

The difference is that in the second scenario you dont have the brackets and there for you're looking for the lower bound of an array of size 2 compared to an integer, and there is no built-in function to compare the two. That's why From_the_hood's code down here works, because it transforms the integer in an array of size 2 (which is probably very bad because hell knows what's the second element) to just then compare it to the rest of the array.

You should probably just implement a binary search manually at this point if i'm being 100% honest, you're using the built in function and then need to decrease the iterator aftewards to correct it. This code is very messy overall and is really overcomplicated. Would you mind sending a link to the problem?

→ Reply