Submission #601635

#	Time	Username	Problem	Language	Result	Execution time	Memory
601635		jack715	Meetings (IOI18_meetings)	C++14	0 / 100	109 ms	23464 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second

using namespace std;

vector<vector<ll> > tree(400005, vector<ll>(3));
vector<int> h;

void build(int indx, int st, int end) {
  if (st == end) {
    if (h[st] == 1)
      tree[indx] = {1, 1, 1};
    else 
      tree[indx] = {0, 0, 0}; 
    return;
  }
  int mid = (st + end) / 2;
  build(indx*2, st, mid);
  build(indx*2+1, mid+1, end);

  if (tree[indx*2][0] == mid-st+1)
    tree[indx][0] = tree[indx*2][0] + tree[indx*2+1][0];
  else 
    tree[indx][0] = tree[indx*2][0];
  

  if (tree[indx*2+1][2] == end-mid)
    tree[indx][2] = tree[indx*2][2] + tree[indx*2+1][2];
  else 
    tree[indx][2] = tree[indx*2][2];
  
  tree[indx][1] = max(max(tree[indx*2][1], tree[indx*2+1][1]), max(tree[indx][0], tree[indx][2]));
  tree[indx][1] = max(tree[indx][1], tree[indx*2][2]+tree[indx*2+1][0]);
}

vector<ll> query(int indx, int st, int end, int l, int r) {
  if (st > r || end < l)
    return {0, 0, 0};
  if (l <= st && end <= r) 
    return tree[indx];
  int mid = (st + end) / 2;
  vector<ll> left = query(indx*2, st, mid, l, r);
  vector<ll> right = query(indx*2+1, mid+1, end, l, r);
  vector<ll> ans(3);

  if (left[0] == mid-st+1)
    ans[0] = left[0] + right[0];
  else 
    ans[0] = left[0];
  

  if (right[2] == end-mid)
    ans[2] = left[2] + right[2];
  else 
    ans[2] = left[2];
  
  ans[1] = max(max(left[1], right[1]), max(ans[0], ans[2]));
  ans[1] = max(ans[1], left[2]+right[0]);
  return ans;
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  int n = H.size(), mx, Q = L.size();
  h = H;
  
  build (1, 0, n-1);
  vector<long long> ans(Q);
  for (int q = 0; q < Q; q++) {
    // vector<ll> ret = query(1, 0, n-1, L[q], R[q]);
    // cout << ret[0] << ' ' << ret[1] << ' ' << ret[2] << '\n';
    ans[q] = (R[q]-L[q]+1)*2 - query(1, 0, n-1, L[q], R[q])[1];
  }
  return ans;
}

/*
3 3
2 1 2
0 0
0 1
0 2
*/

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:70:21: warning: unused variable 'mx' [-Wunused-variable]
   70 |   int n = H.size(), mx, Q = L.size();
      |                     ^~

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