Submission #778262

#	Time	Username	Problem	Language	Result	Execution time	Memory
778262		NeroZein	Meetings (IOI18_meetings)	C++17	17 / 100	73 ms	12320 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"
using namespace std; 

struct node {
  long long ans = 0, sum = 0, pref = 0, suf = 0; 
};

vector<node> seg;

node merge (const node& a, const node& b) {
  node ret;
  ret.sum = a.sum + b.sum;
  ret.suf = max(b.suf, b.sum + a.suf); 
  ret.pref = max(a.pref, a.sum + b.pref); 
  ret.ans = max({a.ans, b.ans, a.suf + b.pref});
  return ret; 
}

void build (int nd, int l, int r, const vector<int>& a) {
  if (l == r) {
    seg[nd].sum = seg[nd].pref = seg[nd].suf = a[l];
    seg[nd].ans = max(0, a[l]); 
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  build(nd + 1, l, mid, a);
  build(rs, mid + 1, r, a);
  seg[nd] = merge(seg[nd + 1], seg[rs]); 
}

node qry (int nd, int l, int r, int s, int e) {
  if (l >= s && r <= e) {
    return seg[nd];
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return qry(nd + 1, l, mid, s, e);
  } else {
    if (mid < s) {
      return qry(rs, mid + 1, r, s, e); 
    } else {
      node lx = qry(nd + 1, l, mid, s, e);
      node rx = qry(rs, mid + 1, r, s, e);
      return merge(lx, rx); 
    }
  }
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int n = (int) H.size();
  int q = L.size();
  seg.resize(2 * n - 1); 
  vector<int> rng(n); 
  for (int i = 0; i < n; ++i) {
    if (H[i] == 1) {
      rng[i] = 1;
    } else {
      rng[i] = -1e9;
    }
  }
  build(0, 0, n - 1, rng); 
  vector<long long> ans(q); 
  for (int i = 0; i < q; ++i) {
    int x = qry(0, 0, n - 1, L[i], R[i]).ans; 
    ans[i] = x + (R[i] - L[i] + 1 - x) * 2; 
  }
  return ans;
}

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