Submission #475545

#	Time	Username	Problem	Language	Result	Execution time	Memory
475545		nafis_shifat	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	1657 ms	365388 KiB

worst_reporter2

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn=2e5+5;
const int inf=1e9;
 
 
ll c[mxn];
int h[mxn];
vector<int> adj[mxn];
 
map<int,ll> mp[mxn];
 
int sz[mxn];
int in[mxn],out[mxn],inv[mxn];
int T = 0;
int n;
 
void dfs0(int u) {
    sz[u] = 1;
    in[u] = ++T;
    inv[T] = u;
    for(int v : adj[u]) {
        dfs0(v);
        sz[u] += sz[v];
    }
    out[u] = T;
}


struct segtree {
    ll tree[4*mxn];
    ll lazy[4*mxn];

    void init() {
        memset(tree, 0, sizeof tree);
        memset(lazy, -1, sizeof lazy);
    }

    void propogate(int node, int left,int right) {
       
        

        if(lazy[node] != -1) {
            lazy[left] = lazy[node];
            lazy[right] = lazy[node];
            tree[left] = 0;
            tree[right] = 0;
            lazy[node] = -1;
        }

        if(tree[node] != 0) {
            tree[left] += tree[node];
            tree[right] += tree[node];
            tree[node] = 0;
        }
    }



    void update(int node,int b,int e,int l,int r,ll v) {
        if(e < l || b > r) return;
        if(b >= l && e <= r) {
            tree[node] += v;
            return;
        }


        int mid = b + e >> 1;
        int left = node << 1;
        int right = left | 1;

        propogate(node,left,right);

        


        update(left, b, mid, l , r, v);
        update(right, mid + 1, e, l, r, v);
    }

    void Set(int node, int b,int e, int l, int r, ll v) {
        if(e < l || b > r) return;
        if(b >= l && e <= r) {
            lazy[node] = v;
            tree[node] = 0;
            return;
        }
        int mid = b + e >> 1;
        int left = node << 1;
        int right = left | 1;

        propogate(node, left, right);

        Set(left, b, mid, l, r, v);
        Set(right, mid + 1, e, l, r, v);

    }

    ll query(int node, int b,int e,int p) {
        if(b == e) return tree[node] + max(0ll,lazy[node]);
        int mid = b + e >> 1;
        int left = node << 1;
        int right = left | 1;

        if(lazy[node] != -1) return tree[node] + lazy[node];

        if(p <= mid) return tree[node] + query(left, b, mid, p);
        return tree[node] + query(right, mid + 1, e, p);
    }

    void add(int l,int r,ll v) {
        update(1,1,n,l,r,v);
    }

    ll query(int p) {
        return query(1,1,n,p);
    }
} st;

 

 
 
 
void dfs(int u, bool keep = false) {
    int mx = -1, bigChild = -1;
 
    // cout<<u<<" "<<keep<<endl;
 
    for(int v : adj[u]) {
        if(sz[v] > mx) {
            mx = sz[v];
            bigChild = v;
        }
    }
    for(int v : adj[u]) if(v != bigChild) dfs(v);
 
    if(bigChild != -1) dfs(bigChild,true);
 
    vector<int> ind;
 
    for(int v : adj[u]) {
        if(v == bigChild) continue;
 
        int last = 0;
        ll mv = mp[v][h[v]];
        for(auto x : mp[v]) {
            ll td = x.s;
            if(x.f < h[v]) td = min(td, mv);
 
            st.add(last + 1, x.f, td);
            last = x.f;
            ind.push_back(x.f);
        }
    }
 
    st.add(1,h[u] - 1, c[u]);
    st.add(h[u] + 1, n, c[u]);
 
    ind.push_back(h[u]);
    ind.push_back(1);
    ind.push_back(n);
 
 
 
    ll nc = st.query(h[u]);


    int lo = 1;
    int hi = h[u] - 1;
    int pos = -1;
    ll rmv = -1;
 
    while(lo <= hi) {
        int mid = lo + hi >> 1;
        ll v = st.query(mid);
        if(v > nc) {
            pos = mid;
            rmv = v;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
 
    if(pos != -1) {
        st.Set(1,1,n, pos, h[u] - 1, nc);
    }
 
    
 
 
    // cout<<"Starting "<<u<<" "<<h[u]<<" "<<c[u]<<endl;
    // for(int i = 1; i <= n; i++) {
    //     cout<<"DP "<<u<<" "<<i<<" = "<<st.query(i)<<endl;
    // }
 
    // cout<<endl<<endl;
    if(!keep) {
        for(int i = in[bigChild]; i <= out[bigChild]; i++) {
            ind.push_back(h[inv[i]]);
        }
        for(int i : ind) {
            mp[u][i] = st.query(i);
        }
        st.Set(1,1,n,1,n,0);
    }
}
 
 
 
 
 
int main() {
    cin >> n;

    st.init();
 
    vector<int> v;
 
    for(int i = 1; i <= n; i++) {
        int bap;
        scanf("%d %d %lld",&bap,&h[i],&c[i]);
        if(bap != i) adj[bap].push_back(i);
        v.push_back(h[i]);
    }
 
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()), v.end());
 
    for(int i = 1; i <= n; i++) {
        h[i] = lower_bound(v.begin(),v.end(),h[i]) - v.begin() + 1;
    }
    dfs0(1);
 
    dfs(1, true);
 
    cout<<st.query(1)<<endl;
 
 
 
 
 
 
 
}

Compilation message (stderr)

worst_reporter2.cpp: In member function 'void segtree::update(int, int, int, int, int, long long int)':
worst_reporter2.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = b + e >> 1;
      |                   ~~^~~
worst_reporter2.cpp: In member function 'void segtree::Set(int, int, int, int, int, long long int)':
worst_reporter2.cpp:92:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |         int mid = b + e >> 1;
      |                   ~~^~~
worst_reporter2.cpp: In member function 'long long int segtree::query(int, int, int, int)':
worst_reporter2.cpp:105:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |         int mid = b + e >> 1;
      |                   ~~^~~
worst_reporter2.cpp: In function 'void dfs(int, bool)':
worst_reporter2.cpp:179:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  179 |         int mid = lo + hi >> 1;
      |                   ~~~^~~~
worst_reporter2.cpp:176:8: warning: variable 'rmv' set but not used [-Wunused-but-set-variable]
  176 |     ll rmv = -1;
      |        ^~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:227:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  227 |         scanf("%d %d %lld",&bap,&h[i],&c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21