Submission #1111941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111941		SalihSahin	Meetings (IOI18_meetings)	C++14	17 / 100	61 ms	11708 KiB

meetings

#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
#include "meetings.h"

const long long inf = 1e17;

struct SEGT{

  struct node{
    int pre, suf, ans, sz;
    node(){
      pre = suf = ans = sz = 0;
    }
  };

  node merge(node a, node b){
    node res = node();

    res.sz = a.sz + b.sz;
    res.pre = a.pre + (a.pre == a.sz ? b.pre : 0);
    res.suf = b.suf + (b.suf == b.sz ? a.suf : 0);
    res.ans = max({a.ans, b.ans, a.suf + b.pre});

    return res;
  }

  vector<node> tree;

  void init(int n){
    tree.assign(4*n, node());
  }

  void build(int ind, int l, int r, vector<int> &a){
    if(l == r){
      tree[ind].sz = 1;
      if(a[l-1] == 1){
        tree[ind].pre = tree[ind].suf = tree[ind].ans = 1;
      }
    }
    else{
      int m = (l + r)/2;
      build(ind*2, l, m, a);
      build(ind*2+1, m+1, r, a);

      tree[ind] = merge(tree[ind*2], tree[ind*2+1]);
    }
  }

  node _query(int ind, int l, int r, int ql, int qr){
    if(l > r || l > qr || r < ql) return node();
    if(l >= ql && r <= qr) return tree[ind];
    else{
      int m = (l + r)/2;

      return merge(_query(ind*2, l, m, ql, qr), _query(ind*2+1, m+1, r, ql, qr));
    }
  }

  int query(int l, int r){
    return _query(1, 1, tree.size()/4, l, r).ans;
  }

};

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int n = H.size();
  SEGT seg;
  seg.init(n);
  seg.build(1, 1, n, H);

  int Q = L.size();
  vector<long long> C(Q);
  for (int j = 0; j < Q; ++j) {
    int ans = 2 * (R[j] - L[j] + 1) - seg.query(L[j] + 1, R[j] + 1);
    C[j] = ans;
  }

  return C;
}

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