oj.uz

답안 #1094196

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1094196 2024-09-28T22:44:56 Z vladilius Worst Reporter 4 (JOI21_worst_reporter4) C++17
79 / 100
 2000 ms 505812 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);
            CC = 0;
        }
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 399412 KB Output is correct
2 Correct 141 ms 399440 KB Output is correct
3 Correct 145 ms 399420 KB Output is correct
4 Correct 142 ms 399576 KB Output is correct
5 Correct 173 ms 401684 KB Output is correct
6 Correct 146 ms 401400 KB Output is correct
7 Correct 149 ms 401388 KB Output is correct
8 Correct 147 ms 401488 KB Output is correct
9 Correct 146 ms 401468 KB Output is correct
10 Correct 165 ms 401524 KB Output is correct
11 Correct 148 ms 401488 KB Output is correct
12 Correct 142 ms 402256 KB Output is correct
13 Correct 139 ms 402128 KB Output is correct
14 Correct 145 ms 401492 KB Output is correct
15 Correct 152 ms 401492 KB Output is correct
16 Correct 158 ms 401744 KB Output is correct
17 Correct 161 ms 401744 KB Output is correct
18 Correct 158 ms 401744 KB Output is correct
19 Correct 155 ms 401744 KB Output is correct
20 Correct 155 ms 401744 KB Output is correct
21 Correct 153 ms 401744 KB Output is correct
22 Correct 152 ms 401216 KB Output is correct
23 Correct 163 ms 401236 KB Output is correct
24 Correct 156 ms 401744 KB Output is correct
25 Correct 154 ms 401744 KB Output is correct
26 Correct 147 ms 402260 KB Output is correct
27 Correct 168 ms 401584 KB Output is correct
28 Correct 155 ms 401744 KB Output is correct
29 Correct 160 ms 402000 KB Output is correct
30 Correct 176 ms 401620 KB Output is correct
31 Correct 151 ms 401744 KB Output is correct

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 399412 KB Output is correct
2 Correct 141 ms 399440 KB Output is correct
3 Correct 145 ms 399420 KB Output is correct
4 Correct 142 ms 399576 KB Output is correct
5 Correct 173 ms 401684 KB Output is correct
6 Correct 146 ms 401400 KB Output is correct
7 Correct 149 ms 401388 KB Output is correct
8 Correct 147 ms 401488 KB Output is correct
9 Correct 146 ms 401468 KB Output is correct
10 Correct 165 ms 401524 KB Output is correct
11 Correct 148 ms 401488 KB Output is correct
12 Correct 142 ms 402256 KB Output is correct
13 Correct 139 ms 402128 KB Output is correct
14 Correct 145 ms 401492 KB Output is correct
15 Correct 152 ms 401492 KB Output is correct
16 Correct 158 ms 401744 KB Output is correct
17 Correct 161 ms 401744 KB Output is correct
18 Correct 158 ms 401744 KB Output is correct
19 Correct 155 ms 401744 KB Output is correct
20 Correct 155 ms 401744 KB Output is correct
21 Correct 153 ms 401744 KB Output is correct
22 Correct 152 ms 401216 KB Output is correct
23 Correct 163 ms 401236 KB Output is correct
24 Correct 156 ms 401744 KB Output is correct
25 Correct 154 ms 401744 KB Output is correct
26 Correct 147 ms 402260 KB Output is correct
27 Correct 168 ms 401584 KB Output is correct
28 Correct 155 ms 401744 KB Output is correct
29 Correct 160 ms 402000 KB Output is correct
30 Correct 176 ms 401620 KB Output is correct
31 Correct 151 ms 401744 KB Output is correct
32 Correct 158 ms 401492 KB Output is correct
33 Correct 1147 ms 485836 KB Output is correct
34 Correct 1152 ms 484424 KB Output is correct
35 Correct 1125 ms 483016 KB Output is correct
36 Correct 1139 ms 484808 KB Output is correct
37 Correct 1164 ms 486220 KB Output is correct
38 Correct 1181 ms 490044 KB Output is correct
39 Correct 820 ms 505812 KB Output is correct
40 Correct 748 ms 505684 KB Output is correct
41 Correct 580 ms 505804 KB Output is correct
42 Correct 740 ms 480204 KB Output is correct
43 Correct 751 ms 480464 KB Output is correct
44 Correct 1195 ms 500428 KB Output is correct
45 Correct 1119 ms 497576 KB Output is correct
46 Correct 804 ms 495304 KB Output is correct
47 Correct 832 ms 484812 KB Output is correct
48 Correct 853 ms 484812 KB Output is correct
49 Correct 633 ms 484828 KB Output is correct
50 Correct 765 ms 464840 KB Output is correct
51 Correct 753 ms 464840 KB Output is correct
52 Correct 711 ms 485836 KB Output is correct
53 Correct 754 ms 485832 KB Output is correct
54 Correct 401 ms 505800 KB Output is correct
55 Correct 775 ms 484220 KB Output is correct
56 Correct 676 ms 494396 KB Output is correct
57 Correct 630 ms 498380 KB Output is correct
58 Correct 452 ms 482760 KB Output is correct
59 Correct 460 ms 482732 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 399412 KB Output is correct
2 Correct 141 ms 399440 KB Output is correct
3 Correct 145 ms 399420 KB Output is correct
4 Correct 142 ms 399576 KB Output is correct
5 Correct 173 ms 401684 KB Output is correct
6 Correct 146 ms 401400 KB Output is correct
7 Correct 149 ms 401388 KB Output is correct
8 Correct 147 ms 401488 KB Output is correct
9 Correct 146 ms 401468 KB Output is correct
10 Correct 165 ms 401524 KB Output is correct
11 Correct 148 ms 401488 KB Output is correct
12 Correct 142 ms 402256 KB Output is correct
13 Correct 139 ms 402128 KB Output is correct
14 Correct 145 ms 401492 KB Output is correct
15 Correct 152 ms 401492 KB Output is correct
16 Correct 158 ms 401744 KB Output is correct
17 Correct 161 ms 401744 KB Output is correct
18 Correct 158 ms 401744 KB Output is correct
19 Correct 155 ms 401744 KB Output is correct
20 Correct 155 ms 401744 KB Output is correct
21 Correct 153 ms 401744 KB Output is correct
22 Correct 152 ms 401216 KB Output is correct
23 Correct 163 ms 401236 KB Output is correct
24 Correct 156 ms 401744 KB Output is correct
25 Correct 154 ms 401744 KB Output is correct
26 Correct 147 ms 402260 KB Output is correct
27 Correct 168 ms 401584 KB Output is correct
28 Correct 155 ms 401744 KB Output is correct
29 Correct 160 ms 402000 KB Output is correct
30 Correct 176 ms 401620 KB Output is correct
31 Correct 151 ms 401744 KB Output is correct
32 Correct 158 ms 401492 KB Output is correct
33 Correct 1147 ms 485836 KB Output is correct
34 Correct 1152 ms 484424 KB Output is correct
35 Correct 1125 ms 483016 KB Output is correct
36 Correct 1139 ms 484808 KB Output is correct
37 Correct 1164 ms 486220 KB Output is correct
38 Correct 1181 ms 490044 KB Output is correct
39 Correct 820 ms 505812 KB Output is correct
40 Correct 748 ms 505684 KB Output is correct
41 Correct 580 ms 505804 KB Output is correct
42 Correct 740 ms 480204 KB Output is correct
43 Correct 751 ms 480464 KB Output is correct
44 Correct 1195 ms 500428 KB Output is correct
45 Correct 1119 ms 497576 KB Output is correct
46 Correct 804 ms 495304 KB Output is correct
47 Correct 832 ms 484812 KB Output is correct
48 Correct 853 ms 484812 KB Output is correct
49 Correct 633 ms 484828 KB Output is correct
50 Correct 765 ms 464840 KB Output is correct
51 Correct 753 ms 464840 KB Output is correct
52 Correct 711 ms 485836 KB Output is correct
53 Correct 754 ms 485832 KB Output is correct
54 Correct 401 ms 505800 KB Output is correct
55 Correct 775 ms 484220 KB Output is correct
56 Correct 676 ms 494396 KB Output is correct
57 Correct 630 ms 498380 KB Output is correct
58 Correct 452 ms 482760 KB Output is correct
59 Correct 460 ms 482732 KB Output is correct
60 Correct 150 ms 399596 KB Output is correct
61 Correct 145 ms 399636 KB Output is correct
62 Correct 140 ms 399416 KB Output is correct
63 Correct 142 ms 399608 KB Output is correct
64 Execution timed out 2080 ms 499960 KB Time limit exceeded
65 Halted 0 ms 0 KB -