Submission #1237850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237850		alexaaa	Wiring (IOI17_wiring)	C++20	0 / 100	157 ms	327680 KiB

wiring

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<set>

using namespace std;

vector<int> st(20);
void build(int node, int r_begin, int r_end, vector<int>&vector){
    if(r_begin == r_end){
        st[node] = vector[r_begin];
        return;
    }
    else{
        int mid = (r_begin+r_end)/2;
        build(2*node,r_begin,mid,vector);
        build(2*node+1,mid+1,r_end,vector);
        st[node] = max(st[2*node],st[2*node+1]);
    }
}
int query(int node, int r_begin, int r_end, int ql, int qr){
    if(r_begin>qr || r_end<ql){
        return 0;
    }
    if(r_begin>=ql && r_end<=qr){
        return st[node];
    }
    int mid = (r_begin+r_end)/2;
    return max(query(2*node,r_begin,mid,ql,qr),query(2*node+1,mid+1,r_end,ql,qr));
}
void update(int node, int r_begin, int r_end, int idx, int val){
    if(r_begin == r_end){
        st[node] = val;
        return;
    }
    else{
        int mid = (r_begin+r_end)/2;
        if(idx<=mid){
            update(2*node,r_begin,mid,idx,val);
        }
        else{
            update(2*node+1,mid+1,r_end,idx,val);
        }
        st[node] = max(st[2*node],st[2*node+1]);
    }
}
long long wire_length(vector<int> &l_a, int l_a_size, vector<int> &s_a, int s_a_size){
    long long length = 0;
    map<int,int> mp;
    vector<pair<int,int>> multiple_connections;
    set<int> s_a_set;
    int size = s_a[s_a_size-1]+1;
    vector<int> plugged(size,0);

    for(int i = 0; i < s_a_size; i++){
        mp.insert({s_a[i],i});
        s_a_set.insert(s_a[i]);
    }
    build(1,0,s_a_size-1,s_a);
    
    for(int j = 0; j < l_a_size; j++){
        auto s = upper_bound(s_a.begin(),s_a.end(),l_a[j]);
        int index = mp[*s];
            if(s==s_a.end()){
                int end_index = s_a_size-1;
                int num = query(1,0,s_a_size-1,0,end_index);
                if(num == 0){
                    length+=abs(s_a[end_index]-l_a[j]);
                    plugged[s_a[end_index]]+=1;
                    if(plugged[s_a[end_index]]==1){
                        s_a_set.erase(s_a[end_index]);
                    }
                }
                else{
                    int max_index = mp[num];
                    
                    length += abs(s_a[max_index] - l_a[j]);
                    plugged[s_a[max_index]] += 1;
                    if( plugged[s_a[max_index]]==1){
                        s_a_set.erase(s_a[max_index]);
                    }
                    update(1,0,s_a_size-1,max_index,0);


                }
                


            }
            else if(index == 0){
                length += abs(s_a[index]-l_a[j]);
                plugged[s_a[index]] += 1;
                if(plugged[s_a[index]] > 1){
                    multiple_connections.push_back({l_a[j],abs(s_a[index]-l_a[j])});
                }
                if(plugged[s_a[index]] == 1){
                    s_a_set.erase(s_a[index]);
                }
                update(1,0,s_a_size-1,index,0);

            }
            else{
                if(plugged[s_a[index-1]]){
                    int num = query(1,0,s_a_size-1,0,index-1);
                    if(num == 0){
                        if(abs(s_a[index-1] - l_a[j]) <= abs(s_a[index] - l_a[j])){
                            length += abs(s_a[index-1] - l_a[j]);
                            plugged[s_a[index-1]] += 1;
                            if( plugged[s_a[index-1]] > 1){
                                multiple_connections.push_back({l_a[j],abs(s_a[index-1]-l_a[j])});

                            }
                            if(plugged[s_a[index-1]] == 1){
                                s_a_set.erase(s_a[index-1]);
                            }

                        }
                        else{
                            length += abs(s_a[index] - l_a[j]);
                            plugged[s_a[index]] += 1;
                            if(plugged[s_a[index]] > 1){
                                multiple_connections.push_back({l_a[j],abs(s_a[index]-l_a[j])});

                            }
                            if(plugged[s_a[index]]==1){
                                s_a_set.erase(s_a[index]);
                            }

                        }
                        
                    }
                    else{ 
                        int max_index = mp[num];
                        length += abs(s_a[max_index] - l_a[j]);
                        plugged[s_a[max_index]] += 1;
                        if(plugged[s_a[max_index]] == 1){
                            s_a_set.erase(s_a[max_index]);
                        }
                        
                        update(1,0,s_a_size-1,max_index,0);

                    }
                   

                }
                else{
                    length += abs(s_a[index-1]-l_a[j]);
                    plugged[s_a[index-1]] += 1;
                    if(plugged[s_a[index-1]] == 1){
                        s_a_set.erase(s_a[index-1]);
                    }
                    update(1,0,s_a_size-1,index-1,0);
                }
            }
    }
    
    int m_c_size = multiple_connections.size();
    for(int u = m_c_size-1; u >= 0; u--){
        if(!s_a_set.empty()){
            auto v = upper_bound(s_a_set.begin(),s_a_set.end(),multiple_connections[u].first);
            if(v == s_a_set.end()){
                continue;
            }
            else{
                length -= multiple_connections[u].second;
                length+=abs(multiple_connections[u].first-*v);
                s_a_set.erase(*v);
            }
        }
        else{
            break;
        }
    }
    return length;
    

    
}

long long min_total_length(vector<int> r, vector<int> b){
    long long length;
    if(r.size() >= b.size()){
        length = wire_length(r,r.size(),b,b.size());
    }
    else{
        length = wire_length(b,b.size(),r,r.size());
    }
    return length;
    

}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45