oj.uz

Submission #986233

# Submission time Handle Problem Language Result Execution time Memory
986233 2024-05-20T06:12:20 Z GrindMachine Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 1327 ms 100708 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

refs:
some solutions

*/

const int MOD = 1e9 + 7;
const int N = 500 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct fenwick {
    int n;
    vector<T> tr;

    fenwick() {

    }

    fenwick(int n_) {
        n = n_;
        tr = vector<T>(n + 1);
    }

    int lsb(int x) {
        return x & -x;
    }

    void pupd(int i, T v) {
        for(; i <= n; i += lsb(i)){
            tr[i] += v;
        }
    }

    T sum(int i) {
        T res = 0;
        for(; i; i ^= lsb(i)){
            res += tr[i];
        }
        return res;
    }

    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }

    int lower_bound(T s){
        // first pos with sum >= s
        if(sum(n) < s) return n+1;
        int i = 0;
        rev(bit,16,0){
            int j = i+(1<<bit);
            if(j > n) conts;
            if(tr[j] < s){
                s -= tr[j];
                i = j;
            }
        }

        return i+1;
    }

    int upper_bound(T s){
        return lower_bound(s+1);
    }
};

vector<pll> adj[N];

ll dfs1(ll u, ll p, ll des, ll mn){
    if(u == des){
        return mn;
    }

    ll ans = inf1;

    for(auto [v,id] : adj[u]){
        if(v == p) conts;
        amin(ans,dfs1(v,u,des,min(mn,id)));
    }

    return ans;
}

ll dfs2(ll u, ll p, ll des, ll mx){
    if(u == des){
        return mx;
    }

    ll ans = 0;

    for(auto [v,id] : adj[u]){
        if(v == p) conts;
        amax(ans,dfs2(v,u,des,max(mx,id)));
    }

    return ans;
}

void solve(int test_case)
{
    ll n,m; cin >> n >> m;
    vector<array<ll,3>> edges(m+5);

    rep1(i,m){
        ll u,v,w; cin >> u >> v >> w;
        edges[i] = {w,u,v};
    }

    sort(edges.begin()+1,edges.begin()+m+1);

    vector<ll> lx(m+5,1), rx(m+5,inf1);

    auto rem = [&](ll id){
        auto [w,u,v] = edges[id];
        adj[u].erase(find(all(adj[u]),make_pair(v,id)));
        adj[v].erase(find(all(adj[v]),make_pair(u,id)));
    };

    // find L[i]
    rep1(i,m){
        auto [w,u,v] = edges[i];
        ll j = dfs1(u,-1,v,inf1);
        if(j <= m){
            rem(j);
            lx[i] = (w+edges[j][0])/2+1;
        }
        adj[u].pb({v,i}), adj[v].pb({u,i});
    }

    // find R[i]
    rep1(i,n) adj[i].clear();

    rev(i,m,1){
        auto [w,u,v] = edges[i];
        ll j = dfs2(u,-1,v,0);
        if(j){
            rem(j);
            rx[i] = (w+edges[j][0])>>1;
        }
        adj[u].pb({v,i}), adj[v].pb({u,i});
    }

    vector<array<ll,3>> events;
    vector<ll> b;

    rep1(i,m){
        ll w = edges[i][0];
        events.pb({lx[i],1,w});
        events.pb({rx[i],3,w});
        b.pb(w);
    }

    ll q; cin >> q;
    rep1(id,q){
        ll x; cin >> x;
        events.pb({x,2,id});
        b.pb(x);
    }

    b.pb(0);
    sort(all(b));
    b.resize(unique(all(b))-b.begin());
    ll siz = sz(b)-1;
    fenwick<ll> fenw_cnt(siz+5), fenw_sum(siz+5);

    auto f = [&](ll x){
        return lower_bound(all(b),x)-b.begin();
    };

    sort(all(events));
    vector<ll> ans(q+5);

    for(auto [x,t,w] : events){
        if(t == 1){
            ll ind = f(w);
            fenw_cnt.pupd(ind,1);
            fenw_sum.pupd(ind,w);
        }
        else if(t == 2){
            ll ind = f(x);
            ll id = w;
            ll lc = fenw_cnt.query(1,ind-1), ls = fenw_sum.query(1,ind-1);
            ll rc = fenw_cnt.query(ind+1,siz), rs = fenw_sum.query(ind+1,siz);
            ans[id] = (x*lc-ls)+rs-(x*rc);
        }
        else{
            ll ind = f(w);
            fenw_cnt.pupd(ind,-1);
            fenw_sum.pupd(ind,-w);
        }
    }

    rep1(i,q) cout << ans[i] << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 852 ms 13828 KB Output is correct
21 Correct 347 ms 14344 KB Output is correct
22 Correct 512 ms 14084 KB Output is correct
23 Correct 562 ms 14048 KB Output is correct
24 Correct 650 ms 14340 KB Output is correct
25 Correct 821 ms 14080 KB Output is correct
26 Correct 868 ms 14092 KB Output is correct
27 Correct 882 ms 13580 KB Output is correct
28 Correct 832 ms 13068 KB Output is correct
29 Correct 573 ms 13844 KB Output is correct
30 Correct 848 ms 13576 KB Output is correct
31 Correct 845 ms 13540 KB Output is correct
32 Correct 848 ms 14348 KB Output is correct
33 Correct 849 ms 13580 KB Output is correct
34 Correct 421 ms 15508 KB Output is correct
35 Correct 871 ms 14092 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 947 ms 89860 KB Output is correct
5 Correct 914 ms 92212 KB Output is correct
6 Correct 889 ms 88984 KB Output is correct
7 Correct 540 ms 91012 KB Output is correct
8 Correct 540 ms 90292 KB Output is correct
9 Correct 534 ms 90816 KB Output is correct
10 Correct 914 ms 99076 KB Output is correct
11 Correct 495 ms 100708 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 464 KB Output is correct
20 Correct 452 ms 74100 KB Output is correct
21 Correct 447 ms 73232 KB Output is correct
22 Correct 444 ms 73188 KB Output is correct
23 Correct 430 ms 73904 KB Output is correct
24 Correct 445 ms 73024 KB Output is correct
25 Correct 435 ms 73336 KB Output is correct
26 Correct 447 ms 73952 KB Output is correct
27 Correct 451 ms 73292 KB Output is correct
28 Correct 463 ms 73528 KB Output is correct
29 Correct 451 ms 73340 KB Output is correct
30 Correct 448 ms 73044 KB Output is correct
31 Correct 439 ms 73180 KB Output is correct
32 Correct 459 ms 73996 KB Output is correct
33 Correct 461 ms 72952 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 852 ms 13828 KB Output is correct
21 Correct 347 ms 14344 KB Output is correct
22 Correct 512 ms 14084 KB Output is correct
23 Correct 562 ms 14048 KB Output is correct
24 Correct 650 ms 14340 KB Output is correct
25 Correct 821 ms 14080 KB Output is correct
26 Correct 868 ms 14092 KB Output is correct
27 Correct 882 ms 13580 KB Output is correct
28 Correct 832 ms 13068 KB Output is correct
29 Correct 573 ms 13844 KB Output is correct
30 Correct 848 ms 13576 KB Output is correct
31 Correct 845 ms 13540 KB Output is correct
32 Correct 848 ms 14348 KB Output is correct
33 Correct 849 ms 13580 KB Output is correct
34 Correct 421 ms 15508 KB Output is correct
35 Correct 871 ms 14092 KB Output is correct
36 Correct 852 ms 14724 KB Output is correct
37 Correct 361 ms 14640 KB Output is correct
38 Correct 528 ms 14892 KB Output is correct
39 Correct 602 ms 14080 KB Output is correct
40 Correct 676 ms 14332 KB Output is correct
41 Correct 822 ms 14300 KB Output is correct
42 Correct 854 ms 14592 KB Output is correct
43 Correct 863 ms 14304 KB Output is correct
44 Correct 843 ms 13068 KB Output is correct
45 Correct 569 ms 14104 KB Output is correct
46 Correct 852 ms 14808 KB Output is correct
47 Correct 863 ms 14096 KB Output is correct
48 Correct 870 ms 14080 KB Output is correct
49 Correct 857 ms 14604 KB Output is correct
50 Correct 445 ms 17068 KB Output is correct
51 Correct 890 ms 14340 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 852 ms 13828 KB Output is correct
21 Correct 347 ms 14344 KB Output is correct
22 Correct 512 ms 14084 KB Output is correct
23 Correct 562 ms 14048 KB Output is correct
24 Correct 650 ms 14340 KB Output is correct
25 Correct 821 ms 14080 KB Output is correct
26 Correct 868 ms 14092 KB Output is correct
27 Correct 882 ms 13580 KB Output is correct
28 Correct 832 ms 13068 KB Output is correct
29 Correct 573 ms 13844 KB Output is correct
30 Correct 848 ms 13576 KB Output is correct
31 Correct 845 ms 13540 KB Output is correct
32 Correct 848 ms 14348 KB Output is correct
33 Correct 849 ms 13580 KB Output is correct
34 Correct 421 ms 15508 KB Output is correct
35 Correct 871 ms 14092 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 947 ms 89860 KB Output is correct
40 Correct 914 ms 92212 KB Output is correct
41 Correct 889 ms 88984 KB Output is correct
42 Correct 540 ms 91012 KB Output is correct
43 Correct 540 ms 90292 KB Output is correct
44 Correct 534 ms 90816 KB Output is correct
45 Correct 914 ms 99076 KB Output is correct
46 Correct 495 ms 100708 KB Output is correct
47 Correct 0 ms 464 KB Output is correct
48 Correct 452 ms 74100 KB Output is correct
49 Correct 447 ms 73232 KB Output is correct
50 Correct 444 ms 73188 KB Output is correct
51 Correct 430 ms 73904 KB Output is correct
52 Correct 445 ms 73024 KB Output is correct
53 Correct 435 ms 73336 KB Output is correct
54 Correct 447 ms 73952 KB Output is correct
55 Correct 451 ms 73292 KB Output is correct
56 Correct 463 ms 73528 KB Output is correct
57 Correct 451 ms 73340 KB Output is correct
58 Correct 448 ms 73044 KB Output is correct
59 Correct 439 ms 73180 KB Output is correct
60 Correct 459 ms 73996 KB Output is correct
61 Correct 461 ms 72952 KB Output is correct
62 Correct 852 ms 14724 KB Output is correct
63 Correct 361 ms 14640 KB Output is correct
64 Correct 528 ms 14892 KB Output is correct
65 Correct 602 ms 14080 KB Output is correct
66 Correct 676 ms 14332 KB Output is correct
67 Correct 822 ms 14300 KB Output is correct
68 Correct 854 ms 14592 KB Output is correct
69 Correct 863 ms 14304 KB Output is correct
70 Correct 843 ms 13068 KB Output is correct
71 Correct 569 ms 14104 KB Output is correct
72 Correct 852 ms 14808 KB Output is correct
73 Correct 863 ms 14096 KB Output is correct
74 Correct 870 ms 14080 KB Output is correct
75 Correct 857 ms 14604 KB Output is correct
76 Correct 445 ms 17068 KB Output is correct
77 Correct 890 ms 14340 KB Output is correct
78 Correct 1327 ms 92148 KB Output is correct
79 Correct 766 ms 91512 KB Output is correct
80 Correct 949 ms 88912 KB Output is correct
81 Correct 1024 ms 92352 KB Output is correct
82 Correct 1102 ms 89512 KB Output is correct
83 Correct 1255 ms 92192 KB Output is correct
84 Correct 1287 ms 87928 KB Output is correct
85 Correct 1289 ms 87644 KB Output is correct
86 Correct 1240 ms 89032 KB Output is correct
87 Correct 909 ms 91844 KB Output is correct
88 Correct 1280 ms 97884 KB Output is correct
89 Correct 1279 ms 97080 KB Output is correct
90 Correct 1320 ms 97468 KB Output is correct
91 Correct 1269 ms 98440 KB Output is correct
92 Correct 762 ms 96188 KB Output is correct
93 Correct 1278 ms 97984 KB Output is correct