Submission #597104

#	Time	Username	Problem	Language	Result	Execution time	Memory
597104		yutabi	Meetings (IOI18_meetings)	C++14	17 / 100	97 ms	10392 KiB

meetings

#include "meetings.h"


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


#define pb push_back


typedef long long ll;



struct Node
{
    int left_count;
    int right_count;

    int best_count;

    bool pass_through;
};




Node seg_tree[400007];



int N;

vector <int> h;


Node merge(Node l, Node r)
{
    Node nw;

    nw.pass_through=0;

    nw.left_count=l.left_count;
    nw.right_count=r.right_count;

    nw.best_count=max(l.right_count+r.left_count,max(l.best_count,r.best_count));

    if(l.pass_through && r.pass_through)
    {
        nw.pass_through=1;
    }

    if(l.pass_through)
    {
        nw.left_count+=r.left_count;
    }

    if(r.pass_through)
    {
        nw.right_count+=l.right_count;
    }

    return nw;
}



Node build(int l=0, int r=N-1, int node=1)
{
    if(l==r)
    {
        if(h[l]==1)
        {
            seg_tree[node].left_count=seg_tree[node].right_count=seg_tree[node].best_count=1;
            seg_tree[node].pass_through=1;
        }

        else
        {
            seg_tree[node].left_count=seg_tree[node].right_count=seg_tree[node].best_count=0;
            seg_tree[node].pass_through=0;
        }

        return seg_tree[node];
    }

    int m=(l+r)/2;

    seg_tree[node]=merge(build(l,m,node*2),build(m+1,r,node*2+1));

    return seg_tree[node];
}

Node query(int hl, int hr, int l=0, int r=N-1, int node=1)
{
    if(hl<=l && r<=hr)
    {
        return seg_tree[node];
    }

    int m=(l+r)/2;

    Node nw;

    nw.left_count=nw.right_count=nw.best_count=0;
    nw.pass_through=1;

    if(hl<=m)
    {
        nw=merge(query(hl,hr,l,m,node*2),nw);
    }

    if(m+1<=hr)
    {
        nw=merge(nw,query(hl,hr,m+1,r,node*2+1));
    }

    return nw;
}



std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
    N = H.size();
    h=H;

    build();

    vector <ll> ans;

    for(int i=0;i<L.size();i++)
    {
        Node res=query(L[i],R[i]);

        ans.pb((R[i]-L[i]+1)*2-res.best_count);
    }



    return ans;
}

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:132:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int i=0;i<L.size();i++)
      |                 ~^~~~~~~~~

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