fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef LOCAL
  5. #define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
  6. #else
  7. #define DEBUG(...) 6
  8. #endif
  9.  
  10. template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
  11. template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
  12. ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
  13. template<typename T> void debug(string s, T x) {cerr << "\033[1;35m" << s << "\033[0;32m = \033[33m" << x << "\033[0m\n";}
  14. template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
  15. if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;35m" << s.substr(0, i) << "\033[0;32m = \033[33m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
  16.  
  17. template<typename T>
  18. struct BIT {
  19.     int n, lg;
  20.     vector<T> bit;
  21.  
  22.     BIT(int _n) : n(_n), lg(__lg(n)), bit(n + 1) {}
  23.  
  24.     BIT(const vector<T> &a) : n((int) a.size()), lg(__lg(n)), bit(n + 1) {
  25.         for (int i=1; i<=n; i++) {
  26.             bit[i] += a[i-1];
  27.             if (i + (i & -i) <= n)
  28.                 bit[i+(i&-i)] += bit[i];
  29.         }
  30.     }
  31.  
  32.     T query(int i) {
  33.         T ret = 0;
  34.         for (i++; i>0; i-=i&-i)
  35.             ret += bit[i];
  36.         return ret;
  37.     }
  38.  
  39.     T query(int l, int r) {
  40.         return l > r ? 0 : query(r) - query(l - 1);
  41.     }
  42.  
  43.     void update(int i, T val) {
  44.         for (i++; i<=n; i+=i&-i)
  45.             bit[i] += val;
  46.     }
  47.  
  48.     int kth(T k) {
  49.         int ret = 0;
  50.         for (int i=lg; i>=0; i--) {
  51.             ret += 1 << i;
  52.             if (ret <= n && bit[ret] < k)
  53.                 k -= bit[ret];
  54.             else
  55.                 ret -= 1 << i;
  56.         }
  57.         return ret;
  58.     }
  59. };
  60.  
  61. const int MAXC = 200;
  62.  
  63. int main() {
  64.     ios_base::sync_with_stdio(false);
  65.     cin.tie(NULL);
  66.  
  67.     int t;
  68.     cin >> t;
  69.     while (t--) {
  70.         int n;
  71.         cin >> n;
  72.         vector<array<int, 4>> pts;
  73.         vector<int> compress;
  74.         for (int i=0; i<n; i++) {
  75.             int l, r, c;
  76.             cin >> l >> r >> c;
  77.             pts.push_back({l, -r, i, c});
  78.             pts.push_back({r, -l, i + n, c});
  79.             compress.push_back(l);
  80.             compress.push_back(r);
  81.         }
  82.  
  83.         sort(compress.begin(), compress.end());
  84.         compress.erase(unique(compress.begin(), compress.end()), compress.end());
  85.         int o = (int) compress.size();
  86.  
  87.         sort(pts.begin(), pts.end());
  88.         vector<vector<int>> dp(o + 1, vector<int>(MAXC + 1, -1e9));
  89.         BIT<int> bit(o);
  90.         dp[o][0] = 0;
  91.         int mx = -1;
  92.         for (auto [x, y, i, c] : pts) {
  93.             x = int(lower_bound(compress.begin(), compress.end(), x) - compress.begin());
  94.             y = int(lower_bound(compress.begin(), compress.end(), -y) - compress.begin());
  95.             vector<vector<int>> ndp(o + 1, vector<int>(MAXC + 1, -1e9));
  96.             vector<int> lazy(o + 1, -1e9);
  97.             for (int j=0; j<=o; j++) {
  98.                 int above = bit.query(y, j - 1), nxt = bit.kth(bit.query(y) + 1);
  99.                 for (int k=0; k<=MAXC; k++)
  100.                     if (dp[j][k] >= 0) {
  101.                         if (i < n) {
  102.                             // regular point
  103.                             if (y >= j) {
  104.                                 assert(k != 0);
  105.                                 // set to color k
  106.                                 if (c == 0 || c == k)
  107.                                     ndp[j][k] = max(ndp[j][k], dp[j][k]);
  108.                                 // set to different color
  109.                                 if (c == 0) {
  110.                                     if (nxt == o) {
  111.                                         if (y == mx)
  112.                                             ndp[o][0] = max(ndp[o][0], dp[j][k]);
  113.                                         else
  114.                                             lazy[y] = max(lazy[y], dp[j][k]);
  115.                                     } else {
  116.                                         ndp[nxt][k] = max(ndp[nxt][k], dp[j][k]);
  117.                                     }
  118.                                 } else if (c != k) {
  119.                                     if (nxt == o) {
  120.                                         if (y == mx)
  121.                                             ndp[o][0] = max(ndp[o][0], dp[j][k]);
  122.                                         else
  123.                                             ndp[y][c] = max(ndp[y][c], dp[j][k]);
  124.                                     } else {
  125.                                         ndp[nxt][k] = max(ndp[nxt][k], dp[j][k]);
  126.                                     }
  127.                                 }
  128.                             } else {
  129.                                 // set to color k
  130.                                 if (k != 0 && (c == 0 || c == k)) {
  131.                                     if (above == 0)
  132.                                         ndp[y][k] = max(ndp[y][k], dp[j][k]);
  133.                                     else
  134.                                         ndp[j][k] = max(ndp[j][k], dp[j][k]);
  135.                                 }
  136.                                 // set to different color
  137.                                 if (j == o && y > mx) {
  138.                                     if (c == 0)
  139.                                         lazy[y] = max(lazy[y], dp[j][k]);
  140.                                     else
  141.                                         ndp[y][c] = max(ndp[y][c], dp[j][k]);
  142.                                 } else {
  143.                                     ndp[j][k] = max(ndp[j][k], dp[j][k]);
  144.                                 }
  145.                             }
  146.                         } else {
  147.                             // query point
  148.                             ndp[j][k] = max(ndp[j][k], dp[j][k] + (above == 0 && x >= j));
  149.                         }
  150.                     }
  151.             }
  152.             for (int j=0; j<=o; j++)
  153.                 for (int k=0; k<=MAXC; k++) {
  154.                     if (k > 0)
  155.                         ndp[j][k] = max(ndp[j][k], lazy[j]);
  156.                     dp[j][k] = ndp[j][k];
  157.                 }
  158.             if (i < n) {
  159.                 bit.update(y, 1);
  160.                 mx = max(mx, y);
  161.             }
  162.         }
  163.  
  164.         int ret = 0;
  165.         for (int j=0; j<=o; j++)
  166.             for (int k=0; k<=MAXC; k++)
  167.                 ret = max(ret, dp[j][k]);
  168.         cout << ret << "\n";
  169.     }
  170.  
  171.     return 0;
  172. }
Success #stdin #stdout 0.01s 5412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lxZxoa
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!