Submission #1073721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073721		Gabriel	Meetings (IOI18_meetings)	C++17	21 / 100	91 ms	20572 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
vector<long long> h;
struct Nodo{
  long long r, p, s, suma;
};
vector<Nodo> _rbol;
Nodo Combinar(Nodo a, Nodo b){
  Nodo c;
  c.p = max(a.p, max(a.suma + b.p, 0LL));
  c.s = max(b.s, max(b.suma + a.s, 0LL));
  c.suma = a.suma + b.suma;
  c.r = max(max(a.r, 0LL), max(b.r, a.s + b.p));
  return c;
}
void Crear(long long i, long long f, long long p){
  if(i == f){
    _rbol[p].suma = h[i];
    _rbol[p].p = max(0LL, h[i]);
    _rbol[p].s = _rbol[p].p;
    _rbol[p].r = _rbol[p].p;
  } else {
    long long P = (i + f) / 2;
    Crear(i, P, p * 2);
    Crear(P + 1, f, p * 2 + 1);
    _rbol[p] = Combinar(_rbol[p * 2], _rbol[p * 2 + 1]);
  }
}
Nodo C(long long i, long long f, long long p, long long I, long long D){
  if(i >= I and f <= D) return _rbol[p];
  if(i > D or f < I){
    Nodo AAA;
    AAA.p = -2222LL;
    AAA.s = -2222LL;
    AAA.suma = -2222LL;
    AAA.r = -2222LL;
    return AAA;
  }
  long long P = (i + f) / 2;
  return Combinar(C(i, P, p * 2, I, D), C(P + 1, f, p * 2 + 1, I, D));
}
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
  vector<long long> l, r;
  bool _3 = 1;
  long long n = H.size();
  long long q = L.size();
  for(long long i = 0; i < n; i++){
    h.push_back((long long)H[i]);
    if(h[i] != 1 and h[i] != 2) _3 = 0;
  }
  for(long long i = 0; i < q; i++) l.push_back((long long)L[i]);
  for(long long i = 0; i < q; i++) r.push_back((long long)R[i]);
  vector<long long> c(q);
  if(_3){
    Nodo a;
    a.r = -2222LL;
    a.p = -2222LL;
    a.s = -2222LL;
    a.suma = -2222LL; 
    _rbol.assign(n * 4 + 22, a);
    for(long long i = 0; i < n; i++){
      if(h[i] == 2LL) h[i] = -2222LL;
    }
    n--;
    Crear(0, n, 1);
    for(long long i = 0; i < q; i++){
      c[i] = (r[i] - l[i] + 1LL) * 2 - C(0, n, 1, l[i], r[i]).r;
    }
  } else if(n <= 3022 and q <= 12){
    for(long long i = 0; i < q; i++){
      long long Bien = LLONG_MAX;
      for(long long j = l[i]; j <= r[i]; j++){
        long long Costo = h[j];
        long long Mayor = h[j];
        for(long long k = j - 1; k >= l[i]; k--){
          Mayor = max(Mayor, h[k]);
          Costo += Mayor;
        }
        Mayor = h[j];
        for(long long k = j + 1; k <= r[i]; k++){
          Mayor = max(Mayor, h[k]);
          Costo += Mayor;
        }
        if(Costo < Bien) Bien = Costo;
      }
      c[i] = Bien;
    }
  } 
  return c;
}

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