Guest User

Untitled

a guest
Apr 7th, 2018
145
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5.  
  6. const int N = 100007;
  7. const int NEUTRAL_VALUE = 0;
  8.  
  9. template < class T, class UT, class MERGE_VALUE_VALUE, class MERGE_VALUE_UPDATE >
  10. struct binary_indexed_tree {
  11.     vector < T > tree;
  12.     int n;
  13.     MERGE_VALUE_VALUE merge_values;
  14.     MERGE_VALUE_UPDATE update_value;
  15.     void build_tree(T *arr, int a, int b, int node) {
  16.         if(a>b) return;
  17.         if(a==b) {
  18.             tree[node]=arr[a];
  19.             return;
  20.         }
  21.         build_tree(arr,a,(a+b)>>1,node<<1);
  22.         build_tree(arr,((a+b)>>1)+1,b,(node<<1)|1);
  23.         tree[node]=merge_values(tree[node<<1],tree[(node<<1)|1]);
  24.     }
  25.     void update_tree(int a, int b, int pos, UT value, int node) {
  26.         if(a>b || a>pos || b<pos) return;
  27.         if(a==b) {
  28.             tree[node]=update_value(tree[node],value);
  29.             return;
  30.         }
  31.         update_tree(a,(a+b)>>1,pos,value,node<<1);
  32.         update_tree(((a+b)>>1)+1,b,pos,value,(node<<1)|1);
  33.         tree[node]=merge_values(tree[node<<1],tree[(node<<1)|1]);
  34.     }
  35.     T query_tree(int a, int b, int i, int j, int node) {
  36.         if(a>b || a>j || b<i) return NEUTRAL_VALUE;
  37.         if(a>=i && b<=j) return tree[node];
  38.         return merge_values(query_tree(a,(a+b)>>1,i,j,node<<1),query_tree(((a+b)>>1)+1,b,i,j,(node<<1)|1));
  39.     }
  40.     void initialize(int k) {
  41.         n=k;
  42.         tree.assign(4*n+5,NEUTRAL_VALUE);
  43.     }
  44.     void initialize(T *arr, int k) {
  45.         n=k;
  46.         tree.assign(4*n+5,NEUTRAL_VALUE);
  47.         build_tree(arr,1,n,1);
  48.     }
  49.     void update(int pos, UT value) {
  50.         update_tree(1,n,pos,value,1);
  51.     }
  52.     T query(int l, int r) {
  53.         return query_tree(1,n,l,r,1);
  54.     }
  55. };
  56.  
  57. struct merge_them {
  58.     int operator () (const int &a, const int &b) const {
  59.         return max(a,b);
  60.     }
  61. };
  62.  
  63. int n,m,from[N],to[N],w[N],arr[N];
  64. vector < int > v[N];
  65. binary_indexed_tree < int, int, merge_them, merge_them > it[N];
  66. int ans;
  67.  
  68. int get(int which, int val) {
  69.     vector < int >::iterator itr=upper_bound(v[which].begin(),v[which].end(),val);
  70.     if(itr==v[which].end()) return 0;
  71.     return it[which].query((int)(itr-v[which].begin())+1,(int)(v[which].size()));
  72. }
  73.  
  74. void update(int which, int w, int val) {
  75.     vector < int >::iterator itr=lower_bound(v[which].begin(),v[which].end(),w);
  76.     int idx=(int)(itr-v[which].begin())+1;
  77.     it[which].update(idx,val);
  78. }
  79.  
  80. int main() {
  81.     ios_base::sync_with_stdio(false);
  82.     cin.tie(NULL);
  83.     int i;
  84.  
  85.     scanf("%d %d", &n, &m);
  86.  
  87.     for(i=1;i<=m;i++) {
  88.         scanf("%d %d %d", &from[i], &to[i], &w[i]);
  89.         v[from[i]].push_back(w[i]);
  90.     }
  91.  
  92.     for(i=1;i<=n;i++) {
  93.         sort(v[i].begin(),v[i].end());
  94.         if(v[i].size()>0) {
  95.             it[i].initialize((int)(v[i].size()));
  96.         }
  97.     }
  98.  
  99.     for(i=m;i>=1;i--) {
  100.         int curr=1+get(to[i],w[i]);
  101.         update(from[i],w[i],curr);
  102.         ans=max(ans,curr);
  103.     }
  104.  
  105.     printf("%d\n", ans);
  106.    
  107.     return 0;
  108. }
RAW Paste Data