Submission #1129629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129629		c0det1ger	Nile (IOI24_nile)	C++20	82 / 100	2090 ms	14772 KiB

nile

#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define double long double

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
    int n = W.size();
    int q = E.size();
    int flg = 1;
    for (int x: A){
        if (x != 2){
            flg = 0;
        }
    }
    for (int x: B){
        if (x != 1){
            flg = 0;
        }
    }
    if (flg){
        vector<long long> vec;
        
        sort(W.begin(), W.end());
        int ans = (n / 2 * 2) + 2 * (n % 2);
        priority_queue<pair<int, int>> pq;
        set<int> groups;
        groups.insert(0);
        for (int i = 0; i < n - 1; i++){
            pq.push({W[i + 1] - W[i], i});
        }
        map<int, int> mp;
        set<int> st;
        st.insert(0);
        mp[0] = 2 * n;
        groups.insert(n);
        while (!pq.empty()){
            pair<int, int> p = pq.top();
            pq.pop();
            if ((*groups.upper_bound(p.second + 1) - *prev(groups.upper_bound(p.second + 1))) % 2 != 0){
                ans--;
            }
            if ((*groups.upper_bound(p.second + 1) - (p.second + 1)) % 2 != 0){
                ans++;
            }
            if ((*prev(groups.upper_bound(p.second + 1)) - (p.second + 1)) % 2 != 0){
                ans++;
            }
            st.insert(p.first);
            mp[p.first] = ans;
            groups.insert(p.second + 1);
        }
        for (int x: E){
            if (st.upper_bound(x) == st.end()){
                vec.push_back((n / 2 * 2) + 2 * (n % 2));
            }
            else{
                int y = *st.upper_bound(x);
                vec.push_back(mp[y]);
            }
        }
        return vec;
    }
    
    
    vector<long long> vec;
    vector<pair<int, pair<int, int>>> vv(n);
    for (int i = 0; i < n; i++){
        vv[i].first = W[i];
        vv[i].second.first = A[i];
        vv[i].second.second = B[i];
    }
    sort(vv.begin(), vv.end());
    for (int i = 0; i < n; i++){
        W[i] = vv[i].first;
        A[i] = vv[i].second.first;
        B[i] = vv[i].second.second;
    }
    for (int d: E){
        long long ans = 0;
        for (int i = 0; i < n; i++){
            ans += A[i];
        }
        vector<int> sep;
        sep.push_back(0);
        for (int i = 0; i < n - 1; i++){
            if (W[i + 1] - W[i] > d){
                sep.push_back(i + 1);
            }
        }
        sep.push_back(n);
        for (int i = 1; i < sep.size(); i++){
            if ((sep[i] - sep[i - 1]) % 2 == 0){
                for (int j = sep[i - 1]; j < sep[i]; j++){
                    ans -= (A[j] - B[j]);
                }
            }
            else{
                for (int j = sep[i - 1]; j < sep[i]; j++){
                    ans -= (A[j] - B[j]);
                }
                int mi = 1e9;
                for (int j = sep[i - 1]; j < sep[i]; j++){
                    if ((j - sep[i - 1]) % 2 == 0 || (W[j + 1] - W[j  - 1] <= d)){
                        mi = min(mi, A[j] - B[j]);
                    }
                }
                ans += mi;
            }
        }
        vec.push_back(ans);
    }
    return vec;
}
/*

int main(){
    vector<int> w = {1, 2, 7, 11, 14, 16};
    vector<int> a = {2, 2, 2, 2, 2, 2};
    vector<int> b = {1, 1, 1, 1, 1, 1};
    vector<int> E = {1, 2, 3, 4, 5, 6, 7, 8};
    vector<long long> ans = calculate_costs(w, a, b, E);
    for (int i = 0; i < 8; i ++){
        cout << ans[i] << "\n";
    }
}*/

/*
 ____   ___    ___     ____  _____          ____    ____   ___
|      |   |  |   \   |        |     /|    |       |      |   \
|      |   |  |    |  |____    |      |    |   _   |____  |___/
|      |   |  |    |  |        |      |    |    |  |      |  \
|____  |___|  |___/   |____    |    __|__  |____|  |____  |   \
 
*/

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