oj.uz

Submission #1102336

# Submission time Handle Problem Language Result Execution time Memory
1102336 2024-10-18T02:46:06 Z ro9669 Nile (IOI24_nile) C++17
38 / 100
 79 ms 15636 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
//#include "nile.h"
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(2e5)+7;

int n , q;
ll dp[maxN];
vector<int> w , a , b , e , id;
vector<ll> res;

namespace sub1{
    bool check(){
        return (q <= 5 && n <= 2000);
    }

    void solve(){
        for (int d : e){
            dp[0] = 0;
            for (int i = 0 ; i < n ; i++){
                ll s = 0;
                int x = INT_MAX;
                dp[i + 1] = ll(1e18);
                for (int j = i ; j >= 0 ; j--){
                    s += b[id[j]];
                    x = min(x , a[id[j]] - b[id[j]]);
                    if (w[id[i]] - w[id[j]] <= d){
                        if ((i - j)&1){
                            dp[i + 1] = min(dp[i + 1] , dp[j] + s);
                        }
                        else{
                            dp[i + 1] = min(dp[i + 1] , dp[j] + s + 1ll * x);
                        }
                    }
                    else{
                        break;
                    }
                }
            }
            res.push_back(dp[n]);
        }
    }
}

namespace sub2{
    bool check(){
        return (q <= 5);
    }

    void solve(){
        for (int d : e){
            dp[0] = 0;
            for (int i = 0 ; i < n ; i++){
                dp[i + 1] = dp[i] + 1ll * a[id[i]];
                if (i - 1 >= 0 && w[id[i]] - w[id[i - 1]] <= d){
                    dp[i + 1] = min(dp[i + 1] , dp[i - 1] + 1ll * b[id[i]] + 1ll * b[id[i - 1]]);
                }
                if (i - 2 >= 0 && w[id[i]] - w[id[i - 2]] <= d){
                    dp[i + 1] = min(dp[i + 1] , dp[i - 2] + 1ll * b[id[i]] + 1ll * a[id[i - 1]] + 1ll * b[id[i - 2]]);
                }
            }
            res.push_back(dp[n]);
        }
    }
}

namespace sub3{
    int fa[maxN];
    ll C[maxN] , S[maxN] , X[maxN] , cur_ans = 0;
    vector<pair<int , ii>> event;
    vector<ii> query;

    int root(int x){
        if (fa[x] < 0) return x; else return fa[x] = root(fa[x]);
    }

    void unite(int u , int v){
        u = root(u);
        v = root(v);
        if (u == v) return;
        if (-fa[u] < -fa[v]) swap(u , v);
        fa[u] += fa[v];
        fa[v] = u;
        S[u] += S[v];
        X[u] = min(X[u] , X[v]);
        cur_ans -= C[u] + C[v];
        if ((-fa[u])&1){
            C[u] = S[u] + X[u];
        }
        else{
            C[u] = S[u];
        }
        cur_ans += C[u];
    }

    void solve(){
        for (int i = 0 ; i < n ; i++){
            cur_ans += 1ll * a[id[i]];
            fa[i] = -1;
            C[i] = a[id[i]];
            S[i] = b[id[i]];
            X[i] = a[id[i]] - b[id[i]];
        }
        for (int i = 0 ; i < n - 1 ; i++){
            event.push_back({w[id[i + 1]] - w[id[i]] , {i , i + 1}});
        }
        res.resize(q);
        for (int i = 0 ; i < q ; i++){
            query.push_back({e[i] , i});
        }
        sort(all(query));
        sort(all(event));
        for (int i = 0 , j = -1 ; i < q ; i++){
            while (j + 1 < n - 1 && event[j + 1].fi <= query[i].fi){
                int u = event[j + 1].se.fi;
                int v = event[j + 1].se.se;
                unite(u , v);
                j++;
            }
            res[query[i].se] = cur_ans;
        }
    }
}

vector<long long> calculate_costs(vector<int> _w , vector<int> _a , vector<int> _b , vector<int> _e){
    w = _w; a = _a; b = _b; e = _e;
    n = sz(w) , q = sz(e);
    id.resize(n);
    for (int i = 0 ; i < n ; i++) id[i] = i;
    sort(all(id) , [](int x , int y){
         return w[x] < w[y];
    });
//    if (sub1::check()){
//        sub1::solve();
//        return res;
//    }
//    if (sub2::check()){
//        sub2::solve();
//        return res;
//    }
    sub3::solve();
    return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB Output is correct

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 2 ms 6736 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 2 ms 6904 KB Output is correct
5 Correct 3 ms 6736 KB Output is correct
6 Correct 2 ms 6736 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12184 KB Output is correct
2 Correct 37 ms 12164 KB Output is correct
3 Correct 37 ms 12164 KB Output is correct
4 Correct 38 ms 12320 KB Output is correct
5 Correct 37 ms 12236 KB Output is correct
6 Correct 41 ms 12244 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 2 ms 6736 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 2 ms 6904 KB Output is correct
5 Correct 3 ms 6736 KB Output is correct
6 Correct 2 ms 6736 KB Output is correct
7 Incorrect 2 ms 6736 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 2 ms 6736 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 2 ms 6904 KB Output is correct
5 Correct 3 ms 6736 KB Output is correct
6 Correct 2 ms 6736 KB Output is correct
7 Incorrect 29 ms 12244 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12184 KB Output is correct
2 Correct 37 ms 12164 KB Output is correct
3 Correct 37 ms 12164 KB Output is correct
4 Correct 38 ms 12320 KB Output is correct
5 Correct 37 ms 12236 KB Output is correct
6 Correct 41 ms 12244 KB Output is correct
7 Correct 79 ms 15564 KB Output is correct
8 Correct 67 ms 15552 KB Output is correct
9 Correct 59 ms 15552 KB Output is correct
10 Correct 75 ms 15548 KB Output is correct
11 Correct 62 ms 15632 KB Output is correct
12 Correct 58 ms 15632 KB Output is correct
13 Correct 65 ms 15636 KB Output is correct
14 Correct 72 ms 15564 KB Output is correct
15 Correct 72 ms 15492 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB Output is correct
2 Correct 2 ms 6736 KB Output is correct
3 Correct 2 ms 6736 KB Output is correct
4 Correct 2 ms 6736 KB Output is correct
5 Correct 2 ms 6904 KB Output is correct
6 Correct 3 ms 6736 KB Output is correct
7 Correct 2 ms 6736 KB Output is correct
8 Incorrect 29 ms 12244 KB Output isn't correct
9 Halted 0 ms 0 KB -