제출 #1209952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209952		anfi	나일강 (IOI24_nile)	C++20	100 / 100	77 ms	18604 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using int64 = long long;
#define pi pair<int64, int64>
#define artefak pair<pi, pi>
const int64 inf = -(1LL << 40);
const int64 mxn = (1 << 18);
int64 parent[4*mxn],sz[4*mxn],val[mxn*4][2],mx[mxn*4];

int64 find(int n){
    return parent[n] == n ? n : parent[n] = find(parent[n]);
}

int64 hitung(int n){
    if(sz[n]%2 == 0) return 0;
    return max(val[n][n&1], mx[n]);
}
vector<int64> calculate_costs(vector<int> w,vector<int> a, vector<int> b, vector<int> e){
    int n = w.size(), q = e.size();
    if(n == 0){
        return vector<int64>(q, 0);
    }
    int64 sigma_a = 0;
    vector<artefak> item;
    for(int i = 0;i < n; i++){
        item.push_back({{w[i], a[i]}, {b[i], b[i]-a[i]}});
    }
    sort(item.begin(), item.end());
    vector<int64> ans(q, 0);
    vector<pi> q1,q2,que;
    for(int i = 0;i <n; i++){
        sigma_a += item[i].fi.se;
        parent[i] = i;
        sz[i] = 1;
        val[i][i&1] = item[i].se.se;
        mx[i] = inf;
        val[i][(i+1)&1] = inf;
    }
    for(int i = 0; i < n-1; i++) q1.push_back({item[i+1].fi.fi-item[i].fi.fi, i});
    for(int i = 1; i < n-1; i++) q2.push_back({item[i+1].fi.fi-item[i-1].fi.fi, i});
    sort(q1.begin(), q1.end());
    sort(q2.begin(), q2.end());
    for(int i = 0; i < q; i++){
        que.push_back({e[i], i});
    }
    sort(que.begin(), que.end());
    int idx = 0, idx1 = 0;
    for(auto[d, i] : que){
        while(idx < q1.size() && q1[idx].fi <= d){
            int64 u = find(q1[idx].se), v = find(q1[idx].se+1);
            sigma_a += hitung(u)+hitung(v);
            parent[u] = v;
            sz[v] += sz[u];
            val[v][0] = max(val[v][0], val[u][0]);
            val[v][1] = max(val[v][1], val[u][1]);
            mx[v] = max(mx[v], mx[u]);
            sigma_a -= hitung(v);
            idx++;
        }
        while(idx1 < q2.size() && q2[idx1].fi <= d){
            int64 u = find(q2[idx1].se);
            sigma_a += hitung(u);
            mx[u] = max(mx[u], item[q2[idx1].se].se.se);
            sigma_a -= hitung(u);
            idx1++;

        }
        ans[i] = sigma_a;
    }
    return ans;
}

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