oj.uz

Submission #1094193

# Submission time Handle Problem Language Result Execution time Memory
1094193 2024-09-28T22:36:13 Z vladilius Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 553 ms 524288 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>

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

node all[20000000];
int CC = 0;

int nw(){
    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:199: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]
  199 |     while (i < all.size()){
      |            ~~^~~~~~~~~~~~
worst_reporter2.cpp:201: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]
  201 |         while (j < all.size() && all[i] == all[j]){
      |                ~~^~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 470096 KB Output is correct
2 Correct 173 ms 469892 KB Output is correct
3 Correct 167 ms 470100 KB Output is correct
4 Correct 170 ms 469952 KB Output is correct
5 Correct 181 ms 471892 KB Output is correct
6 Correct 184 ms 471892 KB Output is correct
7 Correct 189 ms 471900 KB Output is correct
8 Correct 189 ms 471892 KB Output is correct
9 Correct 190 ms 471888 KB Output is correct
10 Correct 190 ms 472032 KB Output is correct
11 Correct 189 ms 472144 KB Output is correct
12 Correct 182 ms 472660 KB Output is correct
13 Correct 189 ms 472892 KB Output is correct
14 Correct 191 ms 472124 KB Output is correct
15 Correct 184 ms 472148 KB Output is correct
16 Correct 191 ms 472184 KB Output is correct
17 Correct 186 ms 472148 KB Output is correct
18 Correct 183 ms 472144 KB Output is correct
19 Correct 180 ms 472052 KB Output is correct
20 Correct 176 ms 472148 KB Output is correct
21 Correct 176 ms 472148 KB Output is correct
22 Correct 176 ms 471632 KB Output is correct
23 Correct 186 ms 471524 KB Output is correct
24 Correct 176 ms 472144 KB Output is correct
25 Correct 182 ms 472140 KB Output is correct
26 Correct 169 ms 472652 KB Output is correct
27 Correct 191 ms 472144 KB Output is correct
28 Correct 173 ms 472144 KB Output is correct
29 Correct 179 ms 472656 KB Output is correct
30 Correct 173 ms 472128 KB Output is correct
31 Correct 176 ms 472144 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 470096 KB Output is correct
2 Correct 173 ms 469892 KB Output is correct
3 Correct 167 ms 470100 KB Output is correct
4 Correct 170 ms 469952 KB Output is correct
5 Correct 181 ms 471892 KB Output is correct
6 Correct 184 ms 471892 KB Output is correct
7 Correct 189 ms 471900 KB Output is correct
8 Correct 189 ms 471892 KB Output is correct
9 Correct 190 ms 471888 KB Output is correct
10 Correct 190 ms 472032 KB Output is correct
11 Correct 189 ms 472144 KB Output is correct
12 Correct 182 ms 472660 KB Output is correct
13 Correct 189 ms 472892 KB Output is correct
14 Correct 191 ms 472124 KB Output is correct
15 Correct 184 ms 472148 KB Output is correct
16 Correct 191 ms 472184 KB Output is correct
17 Correct 186 ms 472148 KB Output is correct
18 Correct 183 ms 472144 KB Output is correct
19 Correct 180 ms 472052 KB Output is correct
20 Correct 176 ms 472148 KB Output is correct
21 Correct 176 ms 472148 KB Output is correct
22 Correct 176 ms 471632 KB Output is correct
23 Correct 186 ms 471524 KB Output is correct
24 Correct 176 ms 472144 KB Output is correct
25 Correct 182 ms 472140 KB Output is correct
26 Correct 169 ms 472652 KB Output is correct
27 Correct 191 ms 472144 KB Output is correct
28 Correct 173 ms 472144 KB Output is correct
29 Correct 179 ms 472656 KB Output is correct
30 Correct 173 ms 472128 KB Output is correct
31 Correct 176 ms 472144 KB Output is correct
32 Correct 177 ms 471960 KB Output is correct
33 Runtime error 553 ms 524288 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 470096 KB Output is correct
2 Correct 173 ms 469892 KB Output is correct
3 Correct 167 ms 470100 KB Output is correct
4 Correct 170 ms 469952 KB Output is correct
5 Correct 181 ms 471892 KB Output is correct
6 Correct 184 ms 471892 KB Output is correct
7 Correct 189 ms 471900 KB Output is correct
8 Correct 189 ms 471892 KB Output is correct
9 Correct 190 ms 471888 KB Output is correct
10 Correct 190 ms 472032 KB Output is correct
11 Correct 189 ms 472144 KB Output is correct
12 Correct 182 ms 472660 KB Output is correct
13 Correct 189 ms 472892 KB Output is correct
14 Correct 191 ms 472124 KB Output is correct
15 Correct 184 ms 472148 KB Output is correct
16 Correct 191 ms 472184 KB Output is correct
17 Correct 186 ms 472148 KB Output is correct
18 Correct 183 ms 472144 KB Output is correct
19 Correct 180 ms 472052 KB Output is correct
20 Correct 176 ms 472148 KB Output is correct
21 Correct 176 ms 472148 KB Output is correct
22 Correct 176 ms 471632 KB Output is correct
23 Correct 186 ms 471524 KB Output is correct
24 Correct 176 ms 472144 KB Output is correct
25 Correct 182 ms 472140 KB Output is correct
26 Correct 169 ms 472652 KB Output is correct
27 Correct 191 ms 472144 KB Output is correct
28 Correct 173 ms 472144 KB Output is correct
29 Correct 179 ms 472656 KB Output is correct
30 Correct 173 ms 472128 KB Output is correct
31 Correct 176 ms 472144 KB Output is correct
32 Correct 177 ms 471960 KB Output is correct
33 Runtime error 553 ms 524288 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -