Submission #1210627

#TimeUsernameProblemLanguageResultExecution timeMemory
1210627PenguinsAreCuteWorst Reporter 4 (JOI21_worst_reporter4)C++17
79 / 100
448 ms114908 KiB
#include <bits/stdc++.h> using namespace std; #define int long long /* template<typename T> struct fenwick { int s; vector<T> ty; fenwick(int _s): s(_s+1), ty(_s+1) {} void up(int x, T yx) { for(++x;x<s;x+=(x&(-x))) ty[x] += yx; } T qry(int x) { T yx = 0; for(++x;x;x-=(x&(-x))) yx += ty[x]; return yx; } int last(T yx) { int ans = 0; for(int i=31-__builtin_clz(s);i;i--) if((ans|(1<<i))<s && ty[ans|(1<<i)] < yx) yx-=T[ans|=(1<<i)]; return ans; } }; */ mt19937 rng(69); struct node { node *l, *r; int pri, key, val, sz; long long sum; node(int x, int v): pri(rng()), key(x), val(v), sz(1), sum(v), l(NULL), r(NULL) {} }; long long sum(node *x) {return x?x->sum:0;} int sz(node *x) {return x?x->sz:0;} void comp(node *x) { x->sum = sum(x->l) + sum(x->r) + x->val; x->sz = sz(x->l) + sz(x->r) + 1; } void split(int pt, node *x, node *&l, node *&r) { if(!x) { l=r=NULL; return; } if((x->key) < pt) { split(pt,x->r,x->r,r); comp(x); l=x; } else { split(pt,x->l,l,x->l); comp(x); r=x; } } void merge(node *&x, node *l, node *r) { if(!l||!r) x = (l?l:r); else if(l->pri > r->pri) { merge(l->r,l->r,r); x = l; } else { merge(r->l,l,r->l); x = r; } comp(x); } int bsta(long long s, node *x) { if(!x) return (s<0?-1:1e9); if(sum(x->l)>s) return bsta(s, x->l); if(sum(x->l) + x->val > s) return x->key; return bsta(s-sum(x->l)-x->val,x->r); } template<typename F> void proc(node *x, F f) { if(!x) return; proc(x->l,f); f(x); proc(x->r,f); } signed main() { int n; cin >> n; int a[n], h[n], c[n]; for(int i=0;i<n;i++) { cin >> a[i] >> h[i] >> c[i]; a[i]--; } node* delta[n]; for(int i=0;i<n;i++) delta[i] = NULL; for(int i=n;i--;) { if(0) proc(delta[i],[&i](node *k) { printf("node%ds +%d @%d\n", i, k->val, k->key); }); node *l, *r; split(h[i], delta[i], l, r); merge(r, new node(h[i], c[i]), r); int pt = bsta(sum(l) - c[i], l); node *ll, *lr; split(pt, l, ll, lr); if(sum(lr) > c[i]) merge(ll, ll, new node(pt, sum(lr) - c[i])); merge(delta[i], ll, r); if(0) proc(delta[i],[&i](node *k) { printf("node%dt +%d @%d\n", i, k->val, k->key); }); if(!i) break; if(sz(delta[i]) > sz(delta[a[i]])) swap(delta[i], delta[a[i]]); node *&par = delta[a[i]]; auto ins = [&par](node *k) { node *l, *r; split(k->key, par, l, r); merge(par, l, new node(k->key, k->val)); merge(par, par, r); }; proc(delta[i], ins); } long long ans = -delta[0]->sum; for(int i=0;i<n;i++) ans += c[i]; cout << ans; /* for(int i=n;--i;) sub[a[i]] += sub[i]; hp[0]=0; for(int i=0;i<n;i++) if(adj[i].size()) { pair<int,int> bst = {-1,-1}; for(auto j: adj[i]) bst=max(bst,{sub[j],hp[j]=j}); hp[bst.second] = hp[i]; } */ }

Compilation message (stderr)

worst_reporter2.cpp: In lambda function:
worst_reporter2.cpp:99:38: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   99 |                         printf("node%ds +%d @%d\n", i, k->val, k->key);
      |                                     ~^              ~
      |                                      |              |
      |                                      int            long long int
      |                                     %lld
worst_reporter2.cpp:99:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
   99 |                         printf("node%ds +%d @%d\n", i, k->val, k->key);
      |                                          ~^            ~~~~~~
      |                                           |               |
      |                                           int             long long int
      |                                          %lld
worst_reporter2.cpp:99:47: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
   99 |                         printf("node%ds +%d @%d\n", i, k->val, k->key);
      |                                              ~^                ~~~~~~
      |                                               |                   |
      |                                               int                 long long int
      |                                              %lld
worst_reporter2.cpp: In lambda function:
worst_reporter2.cpp:111:38: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  111 |                         printf("node%dt +%d @%d\n", i, k->val, k->key);
      |                                     ~^              ~
      |                                      |              |
      |                                      int            long long int
      |                                     %lld
worst_reporter2.cpp:111:43: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
  111 |                         printf("node%dt +%d @%d\n", i, k->val, k->key);
      |                                          ~^            ~~~~~~
      |                                           |               |
      |                                           int             long long int
      |                                          %lld
worst_reporter2.cpp:111:47: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
  111 |                         printf("node%dt +%d @%d\n", i, k->val, k->key);
      |                                              ~^                ~~~~~~
      |                                               |                   |
      |                                               int                 long long int
      |                                              %lld
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...