Submission #829519

#	Time	Username	Problem	Language	Result	Execution time	Memory
829519		vnm06	Meetings (IOI18_meetings)	C++14	19 / 100	5603 ms	4996 KiB

meetings

#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;

long long ansLe[750005];
long long ansRi[750005];

map<int, int> mp;

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R)
{
    int Q = L.size();
    std::vector<long long> C(Q);
    for (int j = 0; j < Q; ++j)
    {
        int le=L[j], ri=R[j];
        ansLe[le]=H[le];
        mp.insert({H[le], 1});
        for(int id=le+1; id<=ri; id++)
        {
            ansLe[id]=ansLe[id-1]+H[id];
            map<int, int>::iterator it=mp.begin();
            int br=1;
            while((*it).first<H[id])
            {
                br+=(*it).second;
                ansLe[id]+=(long long)(H[id]-(*it).first)*(*it).second;
                mp.erase(it);
                if(mp.empty()) break;
                it=mp.begin();
            }
            if(!mp.empty() && mp.find(H[id])!=mp.end()) mp[H[id]]+=br;
            else mp.insert({H[id], br});
        }
        mp.clear();


        ansRi[ri]=H[ri];
        mp.insert({H[ri], 1});
        for(int id=ri-1; id>=le; id--)
        {
            ansRi[id]=ansRi[id+1]+H[id];
            map<int, int>::iterator it=mp.begin();
            int br=1;
            while((*it).first<H[id])
            {
                br+=(*it).second;
                ansRi[id]+=(long long)(H[id]-(*it).first)*(*it).second;
                mp.erase(it);
                if(mp.empty()) break;
                it=mp.begin();
            }
            if(!mp.empty() && mp.find(H[id])!=mp.end()) mp[H[id]]+=br;
            else mp.insert({H[id], br});
        }
        mp.clear();
        C[j]=1e18;
        for(int t=le; t<=ri; t++) if(C[j]>ansLe[t]+ansRi[t]-H[t]) C[j]=ansLe[t]+ansRi[t]-H[t];
    }
    return C;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40