Submission #935174

#	Time	Username	Problem	Language	Result	Execution time	Memory
935174		velislavgarkov	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	14 / 100	2056 ms	139220 KiB

worst_reporter2

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_map>
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]);
    vals[x]=move(vals[v[x][0]]);
    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) {
        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=1;
    for (int i=1;i<=n;i++) {
        if (um[kopie[i]]==0) {
            um[kopie[i]]=cnt;
            cnt++;
        }
    }
    for (int i=1;i<=n;i++) h[i]=um[h[i]];
    find_ss(1);
    for (int j=1;j<=4*cnt;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:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i=0;i<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i=1;i<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp: In function 'void find_dp(int)':
worst_reporter2.cpp:115:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i=1;i<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp:136:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (int i=1;i<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~
worst_reporter2.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for (int i=1;i<v[x].size();i++) {
      |                  ~^~~~~~~~~~~~

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