Submission #380689

#	Time	Username	Problem	Language	Result	Execution time	Memory
380689		sad	Meetings (IOI18_meetings)	C++14	17 / 100	112 ms	8672 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;
const int N=100090;
ll n;int h[N],y[N],go[N],tree[N*4];
void build(int ind,int st,int end)
{
    if(st==end)
    {
        tree[ind]=y[st];return ;
    }
    int m=(st+end)/2;
    build(ind*2+1,st,m);
    build(ind*2+2,m+1,end);
    tree[ind]=max(tree[ind*2+1],tree[ind*2+2]);
}
int 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];
    int m=(st+end)/2;
    return max(get(ind*2+1,st,m,l,r),get(ind*2+2,m+1,end,l,r));
}
int solve (int l,int r)
{
    int  z=r-l+1;z*=2;int x=0;//cout<<l<<" "<<r<<endl;
    if(h[r]==2)
    {
        x=get(0,0,n-1,l,r);
        z-=x;
        return z;
    }
    int rr=r-go[r];
    //cout<<l<<" "<<go[r]<<" "<<r<<endl;
    if(rr<l)return (r-l+1);
    x=max(x,r-rr);
    x=max(x,get(0,0,n-1,l,rr));
    z-=x;
    return z;
}
vector<ll>ans;
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
    ans.clear();
    n=H.size();
    for(int i=0;i<n;i++)
        h[i]=H[i];
    for(int i=n-1;i>-1;i--)
    {
        if(h[i]==2)continue;
        y[i]=y[i+1]+1;
    }
    for(int i=0;i<n;i++)
    {
        if(h[i]==2)continue;
        go[i]=go[i-1]+1;
    }
    /*
    for(int i=0;i<n;i++)
    {
        cout<<go[i]<<" "<<y[i]<<endl;
    }
    return ans;*/
    build(0,0,n-1);
    int q=L.size();
    for(int i=0;i<q;i++)
    {
        //cout<<L[i]<<" "<<R[i]<<endl;
        ans.pb(solve(L[i],R[i]));
    }
    return ans;

}
/*
5 5
1 2 1 1 1
0 2
1 3
0 4
1 1
3 3
*/

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