Submission #1177216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177216		ErJ	Nile (IOI24_nile)	C++20	51 / 100	137 ms	26784 KiB

nile

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define vp vector<pp>
#define inf 1000000000000

vi parent;
vi le;
vi oddMin, evenMin, sureMin, cnt;
ll ans = 0;

void init(ll n, vp point){
    parent.clear(); le.clear(); cnt.clear(); sureMin.clear(); oddMin.clear(); evenMin.clear();
    parent.resize(n);
    le.resize(n, 0);
    cnt.resize(n, 1);
    oddMin.resize(n, inf);
    evenMin.resize(n, inf);
    sureMin.resize(n, inf);
    for(int i = 0; i < n; i++){
        parent[i] = i;
        le[i] = point[i].first;
        evenMin[i] = point[i].second;
    }
}

ll find(ll u){
    if(parent[u] != u) parent[u] = find(parent[u]);
    return parent[u];
}

ll query(ll u){
    u = find(u);
    if(cnt[u] % 2 == 0) return 0;
    return min(sureMin[u], evenMin[u]);
}

void merge(ll u, ll v){
    ll ru = find(u);
    ll rv = find(v);
    if(ru == rv){
        return;
    }
    if(le[ru] < le[rv]) swap(ru, rv);
    ans -= (query(ru) + query(rv));
    parent[ru] = rv;
    sureMin[rv] = min(sureMin[rv], sureMin[ru]);

    if(cnt[rv] % 2 == 0){
        evenMin[rv] = min(evenMin[rv], evenMin[ru]);
        oddMin[rv] = min(oddMin[rv], oddMin[ru]);
    }else{
        evenMin[rv] = min(evenMin[rv], oddMin[ru]);
        oddMin[rv] = min(oddMin[rv], evenMin[ru]);
    }
    cnt[rv] += cnt[ru];
    cnt[ru] = 0;
    ans += query(rv);
}


std::vector<long long> calculate_costs(
    std::vector<int> W, std::vector<int> A,
    std::vector<int> B, std::vector<int> E){

    
    ll n = A.size();
    vi C(n);
    vp point(n);
    ans = 0;
    for(int i = 0; i < n; i++){ 
        C[i] = A[i] - B[i];
        ans += A[i];
        point[i] = {W[i], C[i]};
    }
    set<ll> queries;
    map<ll, ll> answer;
    for(int i = 0; i < E.size(); i++){
        queries.insert(E[i]);
    }

    set<pair<ll, pp>> event;
    sort(begin(point), end(point));
    init(n, point);
    for(int i = 0; i < point.size(); i++){
        if(i + 1 < point.size()) {
            event.insert({point[i + 1].first - point[i].first, {1, i}}); //merging components
            if(i > 0) event.insert({point[i + 1].first - point[i - 1].first, {-1, i}});
        }
    }

    for(ll time : queries){
        if(event.size() > 0){
            while((event.size() > 0) && time >= (*event.begin()).first){
                pair<ll, pp> akt = (*event.begin());
                event.erase(event.begin());
                if(akt.second.first == 1){
                    merge(akt.second.second, akt.second.second + 1);
                }else{
                    ll u = akt.second.second;
                    ll ru = find(u);
                    ans -= query(ru);
                    sureMin[ru] = min(sureMin[ru], point[u].second);
                    ans += query(ru);
                }
            }
        }
        answer[time] = ans;
    }
    vi ANS(E.size());
    for(int i = 0; i < E.size(); i++){
        ANS[i] = answer[E[i]];
    }
    return ANS;
}
/*
int main(){
    ll n;
    cin >> n;
    vector<int> W(n), A(n), B(n);
    for(int i = 0; i < n; i++){
        cin >> W[i] >> A[i] >> B[i];
    }
    ll q;
    cin >> q;
    vector<int> E(q);
    for(int i = 0; i < q; i++){
        cin >> E[i];
    }

    vi aaa = calculate_costs(W, A, B, E);
    for(int i = 0; i < q; i++){
        cout << aaa[i] << '\n';
    }
}*/

• 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: 15 / 15
• Subtask 7: 0 / 18