Cod sursa(job #2547391)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 15 februarie 2020 12:13:03
Problema Cutii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("cutii.in");
ofstream fout("cutii.out");

class FenTree2D {
  private:
    int m, n;
    vector<vector<int>> bit;

  public:
    FenTree2D(int m, int n) :
        m(m), n(n), bit(m + 1, vector<int>(n + 1)) { }

    void update(int x, int y, int val) {
        for (int i = x; i <= m; i += i & -i)
            for (int j = y; j <= n; j += j & -j)
                bit[i][j] = max(bit[i][j], val);
    }

    int query(int x, int y) {
        int mx = 0;
        for (int i = x; i >= 1; i -= i & -i)
            for (int j = y; j >= 1; j -= j & -j)
                mx = max(mx, bit[i][j]);
        return mx;
    }

    void erase(int x, int y) {
        for (int i = x; i <= m; i += i & -i)
            for (int j = y; j <= n; j += j & -j)
                bit[i][j] = 0;
    }
};

int main() {
    int n; fin >> n;
    FenTree2D dp(n, n);

    int t; fin >> t;
    while (t--) {
        vector<vector<int>> v(n, vector<int>(3));
        for (int i = 0; i < n; i++)
            fin >> v[i][0] >> v[i][1] >> v[i][2];
        sort(v.begin(), v.end());

        for (int i = 0; i < n; i++)
            dp.update(v[i][1], v[i][2], dp.query(v[i][1] - 1, v[i][2] - 1) + 1);
        fout << dp.query(n, n) << '\n';

        for (int i = 0; i < n; i++)
            dp.erase(v[i][1], v[i][2]);
    }

    fout.close();
    return 0;
}