#include #include #include #include #include #include #include #include #include #include #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) using namespace std; typedef long long ll; const ll MOD=1e9+7; template void chmin(T &a,const T &b){if(a>b) a=b;} template void chmax(T &a,const T &b){if(a used,cmp,vs; vector> ori; vector> v,rv; StronglyConnectedComponents(int n):used(n),cmp(n,-1),v(n),rv(n){} void add_edge(int x,int y){ v[x].push_back(y); rv[y].push_back(x); } void dfs(int x){ used[x]=true; for(auto to:v[x]) if(!used[to]) dfs(to); vs.push_back(x); } void rdfs(int x,int k){ cmp[x]=k; for(auto to:rv[x]) if(cmp[to]==-1) rdfs(to,k); } int scc(){ for(int i=0;i> &g){ g.resize(k); for(int i=0;i> g; vector A,B,C; vector V; vector dp; const ll INF=1e18; vector> ori; void dfs(int now,int par){ if(dp[now]!=0) return; ll res=0; for(auto nex:g[now]){ if(nex==par) continue; dfs(nex,now); if(dp[nex]==-INF){ dp[now]=-INF; return; } chmax(res,dp[nex]); } dp[now]=V[now]+res; } int main(){ cin.tie(0); ios::sync_with_stdio(false); cin>>N; A.resize(N); B.resize(N); C.resize(N); rep(i,N) cin>>A[i]>>B[i]>>C[i]; vector ord(N); rep(i,N) ord[i]=i; sort(ord.begin(),ord.end(),[&](int a,int b){ return A[a] w=A; sort(w.begin(),w.end()); g.resize(2*N); for(int i=0;i0) g[now].push_back(N+z-1); } for(int i=N;i<2*N;i++){ if(i+1<2*N) g[i+1].push_back(i); g[i].push_back(ord[i-N]); } StronglyConnectedComponents scc(2*N); for(int i=0;i<2*N;i++){ for(auto to:g[i]) scc.add_edge(i,to); } int M=scc.scc(); g.clear(); scc.build(M,g); ori=scc.ori; vector num(M,0); rep(i,N) num[scc.cmp[i]]++; V.resize(M,0); dp.resize(M,0); for(int i=0;i1){ V[i]=-INF; dp[i]=-INF; } rep(i,M) if(dp[i]==0) dfs(i,-1); vector ans(N,0); rep(i,M) for(auto p:ori[i]) if(p