Submission #1244367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244367		a4n_	나일강 (IOI24_nile)	C++20	36 / 100	2092 ms	20740 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
ll t, n, q, cur, a[N], b[N], par[N], suma[N], sumb[N], sz[N], w[N], dp[2][2][N], ans[N], L[N], R[N];
ll sum = 0;

int getPar(int v) {return (par[v] == 0 ? v : par[v] = getPar(par[v]));}

void merge(int v, int u) {
    v = getPar(v), u = getPar(u);
    if(v == u) return;
    if(v > u) swap(v, u);

    ll pd[2][2];
    pd[0][0] = pd[0][1] = pd[1][0] = pd[1][1] = 1e18;

    for(int i1=0;i1<2;i1++){
    for(int j1=0;j1<2;j1++) {
        for(int i2=0;i2<2;i2++){
        for(int j2=0;j2<2;j2++) {
            pd[i1][j2]=min(pd[i1][j2], dp[i1][j1][v]+dp[i2][j2][u]);
            if(j1==0&&i2==0) {
                pd[i1][j2]=min(pd[i1][j2], dp[i1][j1][v]+dp[i2][j2][u]-a[R[v]]+b[R[v]]-a[L[u]]+b[L[u]]);
            }
        }
        }        
    }
    }

    if(sz[v]%2 == 0 && sz[u]%2 == 1 && w[L[u]]-w[R[v]-1]<=cur) {
        pd[1][1] = min(pd[1][1], sumb[v] + sumb[u] - b[R[v]] + a[R[v]]);
    }

    if(sz[u]%2 == 0 && sz[v]%2 == 1 && w[L[u]+1]-w[R[v]]<=cur) {
        pd[1][1] = min(pd[1][1], sumb[v] + sumb[u] - b[L[u]] + a[L[u]]);
    }

    sum -= min({dp[0][0][v], dp[1][0][v], dp[1][1][v], dp[0][1][v]});
    sum -= min({dp[0][0][u], dp[1][0][u], dp[1][1][u], dp[0][1][u]});
    
    par[u] = v;
    sz[v] += sz[u];
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)dp[i][j][v] = pd[i][j];
    L[v] = min(L[v], L[u]);
    R[v] = max(R[v], R[u]);
    suma[v] += suma[u];
    sumb[v] += sumb[u];

    sum += min({dp[0][0][v], dp[1][0][v], dp[1][1][v], dp[0][1][v]});
}

vector<long long> calculate_costs(vector<int> _W, vector<int> _A, vector<int> _B, vector<int> _E) {
    n = size(_W), q = size(_E);

    vector<pll> vec, vecq;
    
    for(int i=0; i<n; i++) vec.pb({_W[i], i});
    for(int i=0; i<q; i++) vecq.pb({_E[i], i+1});
    
    sort(all(vec));
    sort(all(vecq));
    for(int i=0; i<n; i++) w[i + 1] = _W[vec[i].S], a[i+1]=_A[vec[i].S], b[i+1]=_B[vec[i].S];

    for(int i=1; i<=n; i++) {
        sz[i] = 1;
        dp[0][0][i] = dp[1][1][i] = 1e18;
        dp[1][0][i] = dp[0][1][i] = a[i];
        L[i] = i, R[i] = i;
        suma[i] = a[i];
        sumb[i] = b[i];
        sum += a[i];
    }

    vector<pll> vecup;
    for(int i=1; i<n; i++) {
        vecup.pb({w[i+1] - w[i], i});
    }
    vector<pll> vv;
    for(int i=2; i<n; i++) {
        vv.pb({w[i+1]-w[i-1], i});
    }
    sort(all(vecup));
    sort(all(vv));

    int ptr = 0, ptr2 = 0;
    for(int i=0; i<size(vecq); i++) {
        cur = vecq[i].F;
        while(ptr < size(vecup) && vecup[ptr].F<=vecq[i].F) {
            merge(vecup[ptr].S, vecup[ptr].S+1);
            ptr ++;
        }
        while(ptr2 < size(vv) && vv[ptr2].F<=vecq[i].F) {
            int x = vv[ptr2].S;
            int v = getPar(x);
            if(sz[v]%2 == 1) {
                sum -= min({dp[0][0][v], dp[1][0][v], dp[1][1][v], dp[0][1][v]});
                dp[1][1][v] = min(sumb[v] - b[x] + a[x], dp[1][1][v]);
                sum += min({dp[0][0][v], dp[1][0][v], dp[1][1][v], dp[0][1][v]});
            }
            ptr2 ++;
        }

        for(int x=1; x<=n; x++) {
            int v = getPar(x);
            if(sz[v]%2 == 1 && L[v] < x && x > R[v] && w[x+1]-w[x-1] <= cur) {
                sum -= min({dp[0][0][v], dp[1][0][v], dp[1][1][v], dp[0][1][v]});
                dp[1][1][v] = min(sumb[v] - b[x] + a[x], dp[1][1][v]);
                sum += min({dp[0][0][v], dp[1][0][v], dp[1][1][v], dp[0][1][v]});
            }
            // ptr2 ++;
        }

        ans[vecq[i].S] = sum;
    }

    vector<ll> res;
    for(int i=1; i<=q; i++) res.pb(ans[i]);

    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18