Submission #380672

#	Time	Username	Problem	Language	Result	Execution time	Memory
380672		sad	Meetings (IOI18_meetings)	C++14	4 / 100	5567 ms	2480 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
ll n;vector<ll >ans;
const ll N=5090;
ll tree[N*4],pa[N],lef[N];
vector<ll>vv,h,w;
vector<ll>v;ll c=0;
void up(int ind,int st,int end,int uind,int x)
{
    if(uind>end||uind<st)return;
    if(st==end)
    {
        tree[ind]=x;
        return;
    }
    int m=(st+end)/2;
    up(ind*2+1,st,m,uind,x);
    up(ind*2+2,m+1,end,uind,x);
    tree[ind]=tree[ind*2+1]+tree[ind*2+2];
}
ll get (int ind,int st,int end,int l,int r)
{
    if(l>end||r<st)return 0;
    if(l<=st&&end<=r)return tree[ind];
    ll m=(st+end)/2;
    return (get(ind*2+1,st,m,l,r)+get(ind*2+2,m+1,end,l,r));
}
ll solve(int l,int r)
{
    v.clear();
    ll mn=1e17;
    ll re=0;
    for(ll  i=l;i<r+1;i++)
    {
        ll r=0;
        int x=v.size();x--;
        while(x>=0&&v[x]<=h[i])
        {
            ll cnt=get(0,0,c-1,v[x],v[x]);
            up(0,0,c-1,v[x],0);
            re-=cnt*pa[v[x]];
            r+=cnt;x--;
        }
        r++;
        v.pb(h[i]);
        re+=r*pa[h[i]];
        lef[i]=re;
        up(0,0,c-1,h[i],r);
    }
    v.clear();
    memset(tree,0,sizeof tree);
    re=0;
    for(ll  i=r;i>l-1;i--)
    {
        ll r=0;
        int x=v.size();x--;
        while(x>=0&&v[x]<=h[i])
        {
            ll cnt=get(0,0,c-1,v[x],v[x]);
            up(0,0,c-1,v[x],0);
            re-=cnt*pa[v[x]];
            r+=cnt;
            x--;
        }
        r++;
        v.pb(h[i]);
        re+=r*pa[h[i]];
        mn=min(mn,lef[i]+re-pa[h[i]]);
        up(0,0,c-1,h[i],r);

    }
    memset(tree,0,sizeof tree);
    memset(lef,0,sizeof lef);
    return mn;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
    ans.clear();
    vv.clear();
    n=H.size();
    for(ll i=0;i<n;i++){
        w.pb(H[i]);
    }
    sort(w.begin(),w.end());
    w.pb(-1);
    for(ll i=1;i<w.size();i++)
    {
        if(w[i]!=w[i-1])vv.pb(w[i-1]);
    }
    for(ll i=0;i<n;i++)
    {
        ll x=lower_bound(vv.begin(),vv.end(),H[i])-vv.begin();
        h.pb(x);
        pa[x]=H[i];
    }
    c=vv.size();
    ll q=L.size();
    for(ll j=0;j<q;j++)
    {
        ans.pb(solve(L[j],R[j]));
    }
    return ans;
}
/*
4 2
2 4 3 5
0 2
1 3
*/

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:90:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(ll i=1;i<w.size();i++)
      |                ~^~~~~~~~~

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