Submission #26050596

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

//#define debug(x) ;
#define debug(x) cerr << #x << " = " << x << "\n";

ostream& operator<<(ostream& cerr, vector<ll> aux) {
  cerr << "[";
  for (auto e : aux) cerr << e << ' ';
  cerr << "]";
  return cerr;
}

typedef pair<int, int> edge;

const int maxN = 200011;

int n, m;
vector<edge> edges;
vector<int> stack;

int main()
{
  //freopen("test.in", "r", stdin);

  cin >> n >> m;
  edges.resize(m);

  for (auto &e: edges) 
    cin >> e.first >> e.second;

  sort(edges.begin(), edges.end(), [](const edge &a, const edge &b) {
    if (a.first == b.first) 
      return a.second > b.second;
    return a.first < b.first;
  });

  for (auto e: edges) {
    int val = e.second;

    auto it = lower_bound(stack.begin(), stack.end(), val);
    if (it == stack.end()) 
      stack.push_back(val);
    else
      *it = val;
  }

  cout << stack.size() << '\n';

  return 0;
}

Submission Info

Judge Result