Submission #1177200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177200		ErJ	Nile (IOI24_nile)	C++20	0 / 100	2095 ms	22316 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 100000000000

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){
        while(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;
}

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