Submission #1190156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190156		NotLinux	나일강 (IOI24_nile)	C++20	100 / 100	80 ms	9664 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
const int inf = 1e9 + 7;
const int N = 1e5 + 7;
int par[N] , len[N] , cand[2][N] , jump[N];
int find(int a){
    if(par[a] == a)return a;
    return par[a] = find(par[a]);
}
void merge(int a , int b){
    a = find(a) , b = find(b);
    if(a == b)return;   
    jump[a] = min(jump[a] , jump[b]);
    cand[0][a] = min(cand[0][a] , cand[len[a] & 1][b]);
    cand[1][a] = min(cand[1][a] , cand[!(len[a] & 1)][b]);
    len[a] += len[b];
    par[b] = a;
}
int getans(int a){
    a = find(a);
    if(len[a] & 1)
        return min(cand[0][a] , jump[a]);
    else 
        return 0;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A,vector<int> B, vector<int> E) {
    iota(par , par + N , 0);
    fill(len , len + N , 1);
    fill(cand[0] , cand[0] + N , 0);
    fill(cand[1] , cand[1] + N , inf);
    fill(jump , jump + N , inf);

    long long cur_ans = 0 , fixated_ans = 0;
    int n = sz(W);
    vector<array<int,2>>arr(n);
    for(int i = 0;i<n;i++){
        arr[i] = {W[i] , A[i] - B[i]};
        fixated_ans += B[i];
    }
    sort(all(arr));
    // cout << "arr : ";for(auto itr : arr)cout << itr[0] << "," << itr[1] << "   ";cout << endl;
    int q = sz(E);
    vector<pair<int,int>>query(q);
    vector<long long> ans(q);
    for(int i = 0;i<q;i++)
        query[i] = {E[i] , i};
    sort(all(query));
    
    priority_queue<array<int,3>>pq;// -cost , ind1 , ind2
    for(int i = 0;i<n-1;i++)
        pq.push({arr[i][0] - arr[i+1][0] , i , i+1});
    for(int i = 0;i<n;i++){
        cand[0][i] = arr[i][1];
        cur_ans += arr[i][1];
    }
    // cout << "fixated_ans : " << fixated_ans << endl;
    // cout << "cur_ans : " << cur_ans << endl;
    for(auto itr : query){
        int qtime = itr.first;
        int qind = itr.second;
        // cout << "query : " << qtime << " " << qind << endl;
        while(!pq.empty() and -pq.top()[0] <= qtime){
            auto tmp = pq.top();
            // cout << "tmp : " << tmp[0] << " " << tmp[1] << " " << tmp[2] << endl;
            pq.pop();
            if(tmp[2] - tmp[1] == 1){
                cur_ans -= getans(tmp[1]);
                cur_ans -= getans(tmp[2]);
                merge(tmp[1] , tmp[2]);
                cur_ans += getans(tmp[1]);
                if(tmp[1] + 2 < n)
                    pq.push({arr[tmp[1]][0] - arr[tmp[1]+2][0] , tmp[1] , tmp[1] + 2});
            }
            else{// == 2
                assert(find(tmp[1]) == find(tmp[2]));
                cur_ans -= getans(tmp[1]);
                int repr = find(tmp[1]);
                jump[repr] = min(jump[repr] , arr[tmp[1]+1][1]);
                cur_ans += getans(tmp[1]);
            }
            // cout << "cur_ans : " << cur_ans << endl;
        }
        ans[qind] = cur_ans + fixated_ans;
    }
    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