oj.uz

Submission #935217

# Submission time Handle Problem Language Result Execution time Memory
935217 2024-02-28T20:20:40 Z velislavgarkov Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 26 ms 17756 KB 
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    using namespace std;
    const int MAXN=2e5+7;
    #pragma optimize ("O3")
    #pragma target ("sse4")
    #define endl '\n'
    #define getchar getchar_unlocked
    struct Node {
        long long mx, lazyadd, lazyset;
    };
    vector <int> v[MAXN];
    set <int> vals;
    vector <pair <int, long long> > dp[MAXN];
    Node tree[4*MAXN];
    long long c[MAXN];
    int h[MAXN], cnt;
    pair <int,int> kopie[MAXN];
    int ss[MAXN];
     
    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) {
        if (ql>r || qr<l) return;
        push_lazy(node,l,r);
     
        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) {
        if (ql>r || qr<l) return;
        push_lazy(node,l,r);
     
        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) {
        if (ql>r || qr<l) return -1;
        push_lazy(node,l,r);
        if (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.insert(h[x]);
            vals.insert(cnt);
            return;
        }
     
        long long cur_res;
        int k;
        cur_res=0;
        for (int i=1;i<v[x].size();++i) {
            find_dp(v[x][i]);
            
            dp[v[x][i]].resize(vals.size());
            k=0;
            for (auto j:vals) {
                dp[v[x][i]][k]={j,query(1,1,cnt,j)};
                k++;
            }
     
            cur_res+=query(1,1,cnt,(*vals.lower_bound(h[x])));
     
            set_update(1,1,cnt,1,cnt,0);
            vals.clear();
        }
        find_dp(v[x][0]);
        cur_res+=query(1,1,cnt,(*vals.lower_bound(h[x])));
     
        for (int i=1;i<v[x].size();++i) {
            for (int j=0;j<dp[v[x][i]].size();++j) {
                int newv=dp[v[x][i]][j].first;
                set_update(1,1,cnt,newv,newv, query(1,1,cnt, (*vals.lower_bound(newv)) ) );
            }
        }
     
        for (int i=1;i<v[x].size();++i) {
            int ch=v[x][i];
            for (int j=0;j<dp[ch].size();++j) {
                if (j==0) add_update(1,1,cnt,1,dp[ch][j].first,dp[ch][j].second);
                else {
                    add_update(1,1,cnt,dp[ch][j-1].first+1,dp[ch][j].first,dp[ch][j].second);
                }
                vals.insert(dp[ch][j].first);
            }
        }
        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.insert(h[x]);
    }
    int read() {
        int res=0;
        char c=getchar();
        while (c<'0' || c>'9') c=getchar();
        while (c>='0' && c<='9') {
            res=res*10+c-'0';
            c=getchar();
        }
        return res;
    }
    int main () {
        int n, par;
        n=read();
        for (int i=1;i<=n;++i) {
            par=read();
            h[i]=read();
            c[i]=read();
            if (i!=1) v[par].push_back(i);
            kopie[i].first=h[i];
            kopie[i].second=i;
        }
        sort(kopie+1,kopie+n+1);
        cnt=0;
        for (int i=1;i<=n;++i) {
            if (kopie[i].first!=kopie[i-1].second) cnt++;
            h[kopie[i].second]=cnt;
        }
        cnt++;
        find_ss(1);
        for (int j=1;j<=4*cnt;++j) {
            tree[j].lazyset=-1;
        }
        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

worst_reporter2.cpp:7: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    7 |     #pragma optimize ("O3")
      | 
worst_reporter2.cpp:8: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    8 |     #pragma target ("sse4")
      | 
worst_reporter2.cpp: In function 'void find_ss(int)':
worst_reporter2.cpp:101:23: 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=0;i<v[x].size();++i) {
      |                      ~^~~~~~~~~~~~
worst_reporter2.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int i=1;i<v[x].size();++i) {
      |                      ~^~~~~~~~~~~~
worst_reporter2.cpp: In function 'void find_dp(int)':
worst_reporter2.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for (int i=1;i<v[x].size();++i) {
      |                      ~^~~~~~~~~~~~
worst_reporter2.cpp:138:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for (int i=1;i<v[x].size();++i) {
      |                      ~^~~~~~~~~~~~
worst_reporter2.cpp:139:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             for (int j=0;j<dp[v[x][i]].size();++j) {
      |                          ~^~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:145:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for (int i=1;i<v[x].size();++i) {
      |                      ~^~~~~~~~~~~~
worst_reporter2.cpp:147:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |             for (int j=0;j<dp[ch].size();++j) {
      |                          ~^~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16476 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 5 ms 16476 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 22 ms 17244 KB Output is correct
6 Correct 23 ms 17748 KB Output is correct
7 Correct 26 ms 17244 KB Output is correct
8 Correct 24 ms 17284 KB Output is correct
9 Correct 24 ms 17336 KB Output is correct
10 Correct 23 ms 17380 KB Output is correct
11 Correct 22 ms 17240 KB Output is correct
12 Incorrect 7 ms 17756 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16476 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 5 ms 16476 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 22 ms 17244 KB Output is correct
6 Correct 23 ms 17748 KB Output is correct
7 Correct 26 ms 17244 KB Output is correct
8 Correct 24 ms 17284 KB Output is correct
9 Correct 24 ms 17336 KB Output is correct
10 Correct 23 ms 17380 KB Output is correct
11 Correct 22 ms 17240 KB Output is correct
12 Incorrect 7 ms 17756 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16476 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 5 ms 16476 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 22 ms 17244 KB Output is correct
6 Correct 23 ms 17748 KB Output is correct
7 Correct 26 ms 17244 KB Output is correct
8 Correct 24 ms 17284 KB Output is correct
9 Correct 24 ms 17336 KB Output is correct
10 Correct 23 ms 17380 KB Output is correct
11 Correct 22 ms 17240 KB Output is correct
12 Incorrect 7 ms 17756 KB Output isn't correct
13 Halted 0 ms 0 KB -