Submission #935169

#TimeUsernameProblemLanguageResultExecution timeMemory
935169velislavgarkovWorst Reporter 4 (JOI21_worst_reporter4)C++14
0 / 100
863 ms524288 KiB
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <unordered_map> #include <cassert> using namespace std; const int MAXN=2e5+10; struct Node { long long mx, lazyadd, lazyset; }; vector <int> v[MAXN]; set <int> vals[MAXN]; vector <long long> dp[MAXN]; Node tree[4*MAXN]; long long c[MAXN]; int h[MAXN], kopie[MAXN], cnt; int ss[MAXN]; unordered_map <int,int> um; void merge_lazy(int par, int ch) { if (tree[par].lazyset!=-1) { tree[ch].lazyset=tree[par].lazyset; tree[ch].lazyadd=0; return; } if (tree[ch].lazyset==-1) tree[ch].lazyadd+=tree[par].lazyadd; else tree[ch].lazyset+=tree[par].lazyadd; } void push_lazy(int node, int l, int r) { if (tree[node].lazyadd==0 && tree[node].lazyset==-1) return; if (tree[node].lazyadd==0) tree[node].mx=tree[node].lazyset; else tree[node].mx+=tree[node].lazyadd; if (l!=r) { merge_lazy(node,node*2); merge_lazy(node,node*2+1); } tree[node].lazyadd=0; tree[node].lazyset=-1; } void add_update(int node, int l, int r, int ql, int qr, long long ch) { push_lazy(node,l,r); if (ql>r || qr<l) return; if (l>=ql && r<=qr) { tree[node].lazyadd=ch; push_lazy(node,l,r); return; } int mid=(l+r)/2; add_update(node*2,l,mid,ql,qr,ch); add_update(node*2+1,mid+1,r,ql,qr,ch); tree[node].mx=max(tree[node*2].mx,tree[node*2+1].mx); } void set_update(int node, int l, int r, int ql, int qr, long long ch) { push_lazy(node,l,r); if (ql>r || qr<l) return; if (l>=ql && r<=qr) { tree[node].lazyset=ch; push_lazy(node,l,r); return; } int mid=(l+r)/2; set_update(node*2,l,mid,ql,qr,ch); set_update(node*2+1,mid+1,r,ql,qr,ch); tree[node].mx=max(tree[node*2].mx,tree[node*2+1].mx); } long long query(int node, int l, int r, int qind) { push_lazy(node,l,r); if (l==r) return tree[node].mx; int mid=(l+r)/2; if (qind<=mid) return query(node*2,l,mid,qind); return query(node*2+1,mid+1,r,qind); } int find_ind(int node, int l, int r, int ql, int qr, long long ch) { push_lazy(node,l,r); if (ql>r || qr<l || tree[node].mx<=ch) return -1; if (l==r) return l; int mid=(l+r)/2; int res=find_ind(node*2,l,mid,ql,qr,ch); if (res!=-1) return res; return find_ind(node*2+1,mid+1,r,ql,qr,ch); } void find_ss(int x) { ss[x]=1; for (int i=0;i<v[x].size();i++) { find_ss(v[x][i]); ss[x]+=ss[v[x][i]]; } for (int i=1;i<v[x].size();i++) { if (ss[v[x][i]]>ss[v[x][0]]) swap(v[x][0],v[x][i]); } } void find_dp(int x) { if (v[x].empty()) { add_update(1,1,cnt,h[x]+1,cnt,c[x]); vals[x].insert(h[x]); vals[x].insert(cnt); return; } long long cur_res; cur_res=0; for (int i=1;i<v[x].size();i++) { find_dp(v[x][i]); dp[v[x][i]].resize(vals[v[x][i]].size()); int k=0; for (auto j:vals[v[x][i]]) { dp[v[x][i]][k]=query(1,1,cnt,j); k++; } auto it=vals[v[x][i]].lower_bound(h[x]); cur_res+=query(1,1,cnt,(*it)); set_update(1,1,cnt,1,cnt,0); } find_dp(v[x][0]); for (auto it=vals[v[x][0]].begin();it!=vals[v[x][0]].end();it++) vals[x].insert((*it)); auto it=vals[x].lower_bound(h[x]); cur_res+=query(1,1,cnt,(*it)); for (int i=1;i<v[x].size();i++) { for (auto j:vals[v[x][i]]) { auto it=vals[x].lower_bound(j); set_update(1,1,cnt,j,j, query(1,1,cnt,(*it)) ); } } for (int i=1;i<v[x].size();i++) { int k=0; for (auto it=vals[v[x][i]].begin();it!=vals[v[x][i]].end();it++,k++) { if (k==0) add_update(1,1,cnt,1,(*it),dp[v[x][i]][k]); else { auto pr=prev(it); add_update(1,1,cnt,(*pr)+1,(*it),dp[v[x][i]][k]); } vals[x].insert((*it)); } } add_update(1,1,cnt,1,cnt,c[x]); int pos=find_ind(1,1,cnt,1,h[x],cur_res); if (pos!=-1 && pos!=cnt) { set_update(1,1,cnt,pos,h[x],cur_res); } vals[x].insert(h[x]); } int main () { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, par; cin >> n; for (int i=1;i<=n;i++) { cin >> par >> h[i] >> c[i]; if (i!=1) v[par].push_back(i); kopie[i]=h[i]; } sort(kopie+1,kopie+n+1); cnt=2; for (int i=1;i<=n;i++) { if (um[kopie[i]]==0) { um[kopie[i]]=cnt; cnt++; } } cnt++; for (int i=1;i<=n;i++) h[i]=um[h[i]]; find_ss(1); for (int j=0;j<4*MAXN;j++) { tree[j].lazyset=-1; tree[j].mx=tree[j].lazyadd=0; } find_dp(1); cout << query(1,1,cnt,1) << endl; return 0; } /* 6 1 6 5 1 3 6 1 8 4 3 4 9 2 2 5 2 5 6 */

Compilation message (stderr)

worst_reporter2.cpp: In function 'void find_ss(int)':
worst_reporter2.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i=0;i<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i=1;i<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp: In function 'void find_dp(int)':
worst_reporter2.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for (int i=1;i<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp:137:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for (int i=1;i<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp:144:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for (int i=1;i<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...