Submission #1210765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210765		Aviansh	Nile (IOI24_nile)	C++20	32 / 100	155 ms	14912 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    long long n = A.size();
    vector<array<long long,3>>boxes(n);
    for(long long i = 0;i<n;i++){
        boxes[i]={W[i],A[i],B[i]};
    }
    sort(boxes.begin(),boxes.end());
    int q = E.size();
    set<pair<long long, int>>diffs;
    for(int i = 0;i<n-1;i++){
        diffs.insert({boxes[i+1][0]-boxes[i][0],i});
    }
    vector<long long>ans(q);
    vector<array<int,2>>queries(q);
    for(int i = 0;i<q;i++){
        queries[i]={E[i],i};
    }
    sort(queries.begin(),queries.end());
    auto it = diffs.begin();
    long long cur = 0;
    set<array<int,2>>rangs;
    for(int i = 0;i<q;i++){
        while(it!=diffs.end()&&(*it).first<=queries[i][0]){
            pair<long long,int>p = *it;
            int ind = p.second;
            rangs.insert({ind,ind});
            cur++;
            auto up = rangs.lower_bound({ind,1000000000});
            if(up!=rangs.end()){
                if((*up)[0]==ind+1){
                    //merge.
                    int t = (*up)[1];
                    int len = t-(*up)[0]+1;
                    cur-=(len+1)/2;
                    rangs.erase(up);
                    cur--;
                    rangs.erase({ind,ind});
                    rangs.insert({ind,t});
                    cur+=(len+2)/2;
                }
                else{
                    //nothing happens
                }
            }
            up=rangs.lower_bound({ind,-1});
            //this contains ind.
            if(up!=rangs.begin()){
                up--;
                //up is now down
                if((*up)[1]==ind-1){
                    //merge
                    int b = (*up)[0];
                    int u = (*up)[1];
                    int len = u-b+1;
                    cur-=(len+1)/2;
                    rangs.erase(up);
                    up=rangs.lower_bound({ind,-1});
                    int ru = (*up)[1];
                    cur-=(ru-(*up)[0]+1+1)/2;
                    rangs.erase(up);
                    rangs.insert({b,ru});
                    cur+=(ru-b+1+1)/2;
                }
                else{
                    //nothing happens
                }
            }
            it++;
        }

        //cur is now number of pairs

        ans[queries[i][1]]=(n-cur)*2;
    }
    return ans;
}

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