Submission #409614

#	Time	Username	Problem	Language	Result	Execution time	Memory
409614		MKopchev	Meetings (IOI18_meetings)	C++14	60 / 100	5530 ms	80392 KiB

meetings

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

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace
*/
struct info
{
    int l,r,av;
    long long outp;

    int left_child,right_child;
};

vector<info> tree;

vector<int> inp;

long long build(int node,int l,int r)
{
    if(l>r)return 0;

    int mx=0;
    for(int j=l;j<=r;j++)
        mx=max(mx,inp[j]);

    vector<int> v={};
    for(int j=l;j<=r;j++)
        if(inp[j]==mx)v.push_back(j);

    int cur=tree.size();

    int av=v[v.size()/2];

    info me;
    me.l=l;
    me.r=r;
    me.av=av;

    tree.push_back(me);

    tree[node].left_child=node+1;

    long long LHS=build(tree.size(),l,av-1)+1LL*mx*(r-av+1);

    tree[node].right_child=tree.size();

    long long RHS=build(tree.size(),av+1,r)+1LL*mx*(av-l+1);

    tree[node].outp=min(LHS,RHS);

    //cout<<l<<" "<<r<<" -> "<<tree[node].outp<<endl;

    return min(LHS,RHS);
}

long long query(int node,int l,int r,int lq,int rq)
{
    if(l>r||lq>rq)return 0;

    if(l==lq&&r==rq)return tree[node].outp;

    int av=tree[node].av;

    if(rq<av)return query(tree[node].left_child,l,tree[node].av-1,lq,rq);

    if(av<lq)return query(tree[node].right_child,tree[node].av+1,r,lq,rq);

    long long LHS=query(tree[node].left_child,l,av-1,lq,av-1)+1LL*(rq-av+1)*inp[tree[node].av];
    long long RHS=query(tree[node].right_child,av+1,r,av+1,rq)+1LL*(av-lq+1)*inp[tree[node].av];

    return min(LHS,RHS);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  inp=H;

  build(0,0,inp.size()-1);

  vector<long long> outp={};

  for(int i=0;i<L.size();i++)
    outp.push_back(query(0,0,inp.size()-1,L[i],R[i]));

  return outp;
}
/*
int main() {
  int N = read_int();
  int Q = read_int();
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    H[i] = read_int();
  }
  std::vector<int> L(Q), R(Q);
  for (int j = 0; j < Q; ++j) {
    L[j] = read_int();
    R[j] = read_int();
  }

  std::vector<long long> C = minimum_costs(H, L, R);
  for (size_t j = 0; j < C.size(); ++j) {
    printf("%lld\n", C[j]);
  }
  return 0;
}
*/

Compilation message (stderr)

meetings.cpp: In function 'long long int build(int, int, int)':
meetings.cpp:42:9: warning: unused variable 'cur' [-Wunused-variable]
   42 |     int cur=tree.size();
      |         ^~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:93:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for(int i=0;i<L.size();i++)
      |               ~^~~~~~~~~

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