oj.uz

Submission #1094195

# Submission time Handle Problem Language Result Execution time Memory
1094195 2024-09-28T22:40:31 Z vladilius Worst Reporter 4 (JOI21_worst_reporter4) C++17
79 / 100
 1667 ms 506028 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const int NN = 17000000;

struct node{
    ll x;
    int l, r, s;
    node(){
        l = r = x = s = 0;
    }
};

node all[NN];
int CC = 0;

int nw(){
    CC++;
    if (CC == NN){
        exit(0);
    }
    all[CC] = node();
    return CC;
}

struct DS{
    vector<pair<int, ll>> vv;
    int rt, N;
    void init(int Ns){
        rt = nw();
        N = Ns;
    }
    int size(){
        return all[rt].s;
    }
    void fn(int v, int tl, int tr){
        if (!all[v].s) return;
        if (tl == tr){
            vv.pb({tl, all[v].x});
            return;
        }
        int tm = (tl + tr) / 2;
        if (all[v].l) fn(all[v].l, tl, tm);
        if (all[v].r) fn(all[v].r, tm + 1, tr);
    }
    void fn(){
        vv.clear();
        fn(rt, 1, N);
    }
    void recalc(int v){
        all[v].x = all[v].s = 0;
        if (all[v].l){
            all[v].x += all[all[v].l].x;
            all[v].s += all[all[v].l].s;
        }
        if (all[v].r){
            all[v].x += all[all[v].r].x;
            all[v].s += all[all[v].r].s;
        }
    }
    void add(int v, int tl, int tr, int& p, ll& x){
        if (tl == tr){
            all[v].x += x;
            all[v].s = 1;
            return;
        }
        int tm = (tl + tr) / 2;
        if (p <= tm){
            if (!all[v].l) all[v].l = nw();
            add(all[v].l, tl, tm, p, x);
        }
        else {
            if (!all[v].r) all[v].r = nw();
            add(all[v].r, tm + 1, tr, p, x);
        }
        recalc(v);
    }
    void add(int l, int r, ll x){
        add(rt, 1, N, l, x);
        r++; x = -x;
        if (r <= N) add(rt, 1, N, r, x);
    }
    void add1(int& p, ll& x){
        add(rt, 1, N, p, x);
    }
    void clear(int& v, int tl, int tr, int l, int r){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            all[v] = node();
            return;
        }
        int tm = (tl + tr) / 2;
        if (all[v].l) clear(all[v].l, tl, tm, l, r);
        if (all[v].r) clear(all[v].r, tm + 1, tr, l, r);
        recalc(v);
    }
    void upd(int v, int tl, int tr, int& p, ll& x){
        if (tl == tr){
            all[v].x = x;
            all[v].s = 1;
            return;
        }
        int tm = (tl + tr) / 2;
        if (p <= tm){
            if (!all[v].l) all[v].l = nw();
            upd(all[v].l, tl, tm, p, x);
        }
        else {
            if (!all[v].r) all[v].r = nw();
            upd(all[v].r, tm + 1, tr, p, x);
        }
        recalc(v);
    }
    void upd(int p, ll x){
        upd(rt, 1, N, p, x);
    }
    void ch(int l, int r, ll x){
        ll S1 = 0, S2 = get(l - 1);
        if (r < N) S1 = get(r + 1);

        if (l < r) clear(rt, 1, N, l + 1, r);
        upd(l, x - S2);
        if (r < N) upd(r + 1, S1 - x);
    }
    ll get(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return all[v].x;
        int tm = (tl + tr) / 2;
        ll out = 0;
        if (all[v].l) out += get(all[v].l, tl, tm, l, r);
        if (all[v].r) out += get(all[v].r, tm + 1, tr, l, r);
        return out;
    }
    ll get(int p){
        if (!p) return 0;
        int l = 1;
        return get(rt, 1, N, l, p);
    }
    int find(int v, int tl, int tr, ll& x, ll p){
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2;
        if (all[v].l && (all[all[v].l].x + p) <= x){
            return find(all[v].r, tm + 1, tr, x, p + all[all[v].l].x);
        }
        return find(all[v].l, tl, tm, x, p);
    }
    vector<arr3> gd;
    void dec(int v, int tl, int tr, int& r){
        if (tl > r) return;
        if (tr <= r){
            gd.pb({v, tl, tr});
            return;
        }
        int tm = (tl + tr) / 2;
        if (all[v].l) dec(all[v].l, tl, tm, r);
        if (all[v].r) dec(all[v].r, tm + 1, tr, r);
    }
    int fn(int v, int tl, int tr, ll& x, ll p){
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2;
        if (!all[v].l) return fn(all[v].r, tm + 1, tr, x, p);
        if (!all[v].r) return fn(all[v].l, tl, tm, x, p);
        if ((p + all[all[v].l].x) <= x){
            return fn(all[v].r, tm + 1, tr, x, p + all[all[v].l].x);
        }
        return fn(all[v].l, tl, tm, x, p);
    }
    int find(ll x, int r){
        gd.clear();
        dec(rt, 1, N, r);
        ll s = 0;
        for (auto [v, tl, tr]: gd){
            if ((s + all[v].x) > x){
                return fn(v, tl, tr, x, s);
            }
            s += all[v].x;
        }
        return 0;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    all[0] = node();
    
    int n; cin>>n;
    vector<int> a(n + 1), h(n + 1), c(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i]>>h[i]>>c[i];
    }
    
    vector<pii> all;
    for (int i = 1; i <= n; i++) all.pb({h[i], i});
    sort(all.begin(), all.end());
    int i = 0, cc = 0;
    while (i < all.size()){
        int j = i;
        while (j < all.size() && all[i] == all[j]){
            j++;
        }
        cc++;
        while (i < j){
            h[all[i].ss] = cc;
            i++;
        }
    }
    
    vector<int> g1[n + 1];
    for (int i = 1; i <= n; i++){
        if (a[i] != i) g1[a[i]].pb(i);
    }
    vector<bool> used(n + 1), seen(n + 1);
    vector<int> dd(n + 1), d[n + 1], st;
    function<void(int)> dfs = [&](int v){
        seen[v] = used[v] = 1;
        st.pb(v);
        for (int i: g1[v]){
            if (used[i]){
                if (seen[i]){
                    for (int j: st){
                        dd[j] = st[0];
                    }
                }
                continue;
            }
            dfs(i);
        }
        seen[v] = 0; st.pop_back();
    };
    
    for (int i = 1; i <= n; i++){
        if (!used[i]){
            dfs(i);
        }
    }
    
    vector<int> g[n + 1];
    for (int i = 1; i <= n; i++){
        if (!dd[i]) dd[i] = i;
        d[dd[i]].pb(i);
    }
    for (int i = 1; i <= n; i++){
        int x = dd[a[i]], y = dd[i];
        if (x != y) g[x].pb(y);
    }
    
    vector<ll> sum(cc + 1);
    vector<int> t;
    DS T[n + 1];
    function<void(int)> solve = [&](int v){
        used[v] = 1;
        for (int i: g[v]) solve(i);
        
        T[v].init(cc);
        for (int i: g[v]){
            if (T[v].size() < T[i].size()) swap(T[v], T[i]);
            T[i].fn();
            for (auto [p, x]: T[i].vv){
                T[v].add1(p, x);
            }
        }
        
        ll S = 0;
        for (int i: d[v]) S += c[i];
        
        t.clear();
        for (int i: d[v]){
            t.pb(h[i]);
            sum[h[i]] = 0;
        }
        for (int i: d[v]) sum[h[i]] += c[i];
        
        sort(t.begin(), t.end());
        int pre = 1;
        for (int i: t){
            if (pre < i){
                T[v].add(pre, i - 1, S);
            }
            pre = i + 1;
            T[v].add(i, i, S - sum[i]);
        }
        if (pre <= cc){
            T[v].add(pre, cc, S);
        }
        
        for (int i: t){
            ll X = T[v].get(i);
            if (i == 1 || T[v].get(i - 1) <= X) continue;
            int r = T[v].find(X, i - 1);
            T[v].ch(r, i - 1, X);
        }
    };
    fill(used.begin(), used.end(), 0);
    ll out = 0;
    for (int i = 1; i <= n; i++){
        if (!used[i]){
            solve(i);
            out += T[i].get(1);
        }
    }
    cout<<out<<"\n";
}

Compilation message

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:204:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |     while (i < all.size()){
      |            ~~^~~~~~~~~~~~
worst_reporter2.cpp:206:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |         while (j < all.size() && all[i] == all[j]){
      |                ~~^~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 399556 KB Output is correct
2 Correct 153 ms 399440 KB Output is correct
3 Correct 146 ms 399408 KB Output is correct
4 Correct 142 ms 399440 KB Output is correct
5 Correct 156 ms 401492 KB Output is correct
6 Correct 154 ms 401488 KB Output is correct
7 Correct 157 ms 401492 KB Output is correct
8 Correct 152 ms 401616 KB Output is correct
9 Correct 153 ms 401516 KB Output is correct
10 Correct 174 ms 401380 KB Output is correct
11 Correct 158 ms 401488 KB Output is correct
12 Correct 158 ms 402260 KB Output is correct
13 Correct 176 ms 402256 KB Output is correct
14 Correct 157 ms 401488 KB Output is correct
15 Correct 165 ms 401468 KB Output is correct
16 Correct 159 ms 401612 KB Output is correct
17 Correct 168 ms 401684 KB Output is correct
18 Correct 161 ms 401660 KB Output is correct
19 Correct 158 ms 401640 KB Output is correct
20 Correct 164 ms 401748 KB Output is correct
21 Correct 148 ms 401712 KB Output is correct
22 Correct 150 ms 401236 KB Output is correct
23 Correct 160 ms 401240 KB Output is correct
24 Correct 157 ms 401748 KB Output is correct
25 Correct 151 ms 401652 KB Output is correct
26 Correct 152 ms 402260 KB Output is correct
27 Correct 161 ms 401492 KB Output is correct
28 Correct 157 ms 401812 KB Output is correct
29 Correct 157 ms 402004 KB Output is correct
30 Correct 168 ms 401568 KB Output is correct
31 Correct 164 ms 401532 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 399556 KB Output is correct
2 Correct 153 ms 399440 KB Output is correct
3 Correct 146 ms 399408 KB Output is correct
4 Correct 142 ms 399440 KB Output is correct
5 Correct 156 ms 401492 KB Output is correct
6 Correct 154 ms 401488 KB Output is correct
7 Correct 157 ms 401492 KB Output is correct
8 Correct 152 ms 401616 KB Output is correct
9 Correct 153 ms 401516 KB Output is correct
10 Correct 174 ms 401380 KB Output is correct
11 Correct 158 ms 401488 KB Output is correct
12 Correct 158 ms 402260 KB Output is correct
13 Correct 176 ms 402256 KB Output is correct
14 Correct 157 ms 401488 KB Output is correct
15 Correct 165 ms 401468 KB Output is correct
16 Correct 159 ms 401612 KB Output is correct
17 Correct 168 ms 401684 KB Output is correct
18 Correct 161 ms 401660 KB Output is correct
19 Correct 158 ms 401640 KB Output is correct
20 Correct 164 ms 401748 KB Output is correct
21 Correct 148 ms 401712 KB Output is correct
22 Correct 150 ms 401236 KB Output is correct
23 Correct 160 ms 401240 KB Output is correct
24 Correct 157 ms 401748 KB Output is correct
25 Correct 151 ms 401652 KB Output is correct
26 Correct 152 ms 402260 KB Output is correct
27 Correct 161 ms 401492 KB Output is correct
28 Correct 157 ms 401812 KB Output is correct
29 Correct 157 ms 402004 KB Output is correct
30 Correct 168 ms 401568 KB Output is correct
31 Correct 164 ms 401532 KB Output is correct
32 Correct 158 ms 401516 KB Output is correct
33 Correct 1137 ms 485812 KB Output is correct
34 Correct 1210 ms 484680 KB Output is correct
35 Correct 1137 ms 482848 KB Output is correct
36 Correct 1157 ms 484892 KB Output is correct
37 Correct 1135 ms 486248 KB Output is correct
38 Correct 1168 ms 490016 KB Output is correct
39 Correct 807 ms 505804 KB Output is correct
40 Correct 759 ms 506028 KB Output is correct
41 Correct 664 ms 505800 KB Output is correct
42 Correct 756 ms 480388 KB Output is correct
43 Correct 735 ms 480008 KB Output is correct
44 Correct 1196 ms 500336 KB Output is correct
45 Correct 1223 ms 497612 KB Output is correct
46 Correct 830 ms 495304 KB Output is correct
47 Correct 850 ms 484772 KB Output is correct
48 Correct 882 ms 484944 KB Output is correct
49 Correct 678 ms 484800 KB Output is correct
50 Correct 818 ms 464844 KB Output is correct
51 Correct 791 ms 464828 KB Output is correct
52 Correct 953 ms 485968 KB Output is correct
53 Correct 805 ms 485836 KB Output is correct
54 Correct 419 ms 505932 KB Output is correct
55 Correct 780 ms 484292 KB Output is correct
56 Correct 702 ms 494460 KB Output is correct
57 Correct 645 ms 498632 KB Output is correct
58 Correct 446 ms 482760 KB Output is correct
59 Correct 445 ms 482760 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 399556 KB Output is correct
2 Correct 153 ms 399440 KB Output is correct
3 Correct 146 ms 399408 KB Output is correct
4 Correct 142 ms 399440 KB Output is correct
5 Correct 156 ms 401492 KB Output is correct
6 Correct 154 ms 401488 KB Output is correct
7 Correct 157 ms 401492 KB Output is correct
8 Correct 152 ms 401616 KB Output is correct
9 Correct 153 ms 401516 KB Output is correct
10 Correct 174 ms 401380 KB Output is correct
11 Correct 158 ms 401488 KB Output is correct
12 Correct 158 ms 402260 KB Output is correct
13 Correct 176 ms 402256 KB Output is correct
14 Correct 157 ms 401488 KB Output is correct
15 Correct 165 ms 401468 KB Output is correct
16 Correct 159 ms 401612 KB Output is correct
17 Correct 168 ms 401684 KB Output is correct
18 Correct 161 ms 401660 KB Output is correct
19 Correct 158 ms 401640 KB Output is correct
20 Correct 164 ms 401748 KB Output is correct
21 Correct 148 ms 401712 KB Output is correct
22 Correct 150 ms 401236 KB Output is correct
23 Correct 160 ms 401240 KB Output is correct
24 Correct 157 ms 401748 KB Output is correct
25 Correct 151 ms 401652 KB Output is correct
26 Correct 152 ms 402260 KB Output is correct
27 Correct 161 ms 401492 KB Output is correct
28 Correct 157 ms 401812 KB Output is correct
29 Correct 157 ms 402004 KB Output is correct
30 Correct 168 ms 401568 KB Output is correct
31 Correct 164 ms 401532 KB Output is correct
32 Correct 158 ms 401516 KB Output is correct
33 Correct 1137 ms 485812 KB Output is correct
34 Correct 1210 ms 484680 KB Output is correct
35 Correct 1137 ms 482848 KB Output is correct
36 Correct 1157 ms 484892 KB Output is correct
37 Correct 1135 ms 486248 KB Output is correct
38 Correct 1168 ms 490016 KB Output is correct
39 Correct 807 ms 505804 KB Output is correct
40 Correct 759 ms 506028 KB Output is correct
41 Correct 664 ms 505800 KB Output is correct
42 Correct 756 ms 480388 KB Output is correct
43 Correct 735 ms 480008 KB Output is correct
44 Correct 1196 ms 500336 KB Output is correct
45 Correct 1223 ms 497612 KB Output is correct
46 Correct 830 ms 495304 KB Output is correct
47 Correct 850 ms 484772 KB Output is correct
48 Correct 882 ms 484944 KB Output is correct
49 Correct 678 ms 484800 KB Output is correct
50 Correct 818 ms 464844 KB Output is correct
51 Correct 791 ms 464828 KB Output is correct
52 Correct 953 ms 485968 KB Output is correct
53 Correct 805 ms 485836 KB Output is correct
54 Correct 419 ms 505932 KB Output is correct
55 Correct 780 ms 484292 KB Output is correct
56 Correct 702 ms 494460 KB Output is correct
57 Correct 645 ms 498632 KB Output is correct
58 Correct 446 ms 482760 KB Output is correct
59 Correct 445 ms 482760 KB Output is correct
60 Correct 150 ms 399568 KB Output is correct
61 Correct 154 ms 399696 KB Output is correct
62 Correct 144 ms 399588 KB Output is correct
63 Correct 151 ms 399424 KB Output is correct
64 Incorrect 1667 ms 488856 KB Output isn't correct
65 Halted 0 ms 0 KB -