Submission #1287012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287012		MMihalev	Nile (IOI24_nile)	C++20	32 / 100	103 ms	13296 KiB

nile

#include<iostream>
#include<algorithm>
#include<tuple>
#include<vector>
#include<set>
#include "nile.h"
using namespace std;
const int MAX_N=1e5+5;
long long a[MAX_N];
long long b[MAX_N];
int w[MAX_N];
int n;

vector<int>v;
int d;
long long dp[MAX_N];
long long solve()
{
    for(int i=1;i<=v.size();i++)
    {
        int id=v[i-1];
        dp[i]=dp[i-1]+a[id];
        if(i>=2)
        {
            dp[i]=min(dp[i],dp[i-2]+b[id]+b[v[i-2]]);
        }
        if(i>=3)
        {
            if(w[id]-w[v[i-3]]<=d)
            {
                dp[i]=min(dp[i],dp[i-3]+b[id]+a[v[i-2]]+b[v[i-3]]);
            }
        }
    }
    return dp[v.size()];
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
    n=W.size();
    vector<pair<int,int>>order;
    for(int i=0;i<n;i++)
    {
        a[i]=A[i];
        b[i]=B[i];
        w[i]=W[i];
        order.push_back({w[i],i});
    }
    sort(order.begin(),order.end());

    vector<pair<int,int>>gaps;

    for(int i=1;i<n;i++)
    {
        gaps.push_back({order[i].first-order[i-1].first,i-1});
    }
    sort(gaps.begin(),gaps.end());

    vector<long long>answers;
    answers.resize((int)(E.size()));
    vector<pair<int,int>>queries;
    for(int i=0;i<E.size();i++)
    {
        queries.push_back({E[i],i});
    }
    sort(queries.begin(),queries.end());

    int idgap=0;

    set<int>posgap;

    long long ans;

    for(int idquery=0;idquery<queries.size();idquery++)
    {
        d=queries[idquery].first;

        if(idquery>0)
        {
            while(idgap<gaps.size() && gaps[idgap].first<=d)
            {
                posgap.erase(gaps[idgap].second);

                int prv,nxt;
                auto it=posgap.upper_bound(gaps[idgap].second);
                nxt=(*it);
                it--;
                prv=(*it);

                int lenprv=gaps[idgap].second-prv;
                int lennxt=nxt-gaps[idgap].second;

                ans-=lenprv%2;ans-=lennxt%2;
                ans+=(nxt-prv)%2;

                idgap++;
            }

            answers[queries[idquery].second]=ans;

            continue;
        }

        while(idgap<gaps.size() && gaps[idgap].first<=d)
        {
            idgap++;
        }
        for(int j=idgap;j<gaps.size();j++)
        {
            posgap.insert(gaps[j].second);
        }
        posgap.insert(-1);
        posgap.insert(n-1);

        ans=0;

        v.clear();
        v.push_back(order[0].second);

        for(int i=1;i<n;i++)
        {
            if(order[i].first-order[i-1].first>d)
            {
                ans+=v.size()+(v.size()%2);
                v.clear();
            }
            v.push_back(order[i].second);
        }
        ans+=v.size()+(v.size()%2);

        answers[queries[idquery].second]=ans;
    }

    return answers;
}

• 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