Submission #720499

#	Time	Username	Problem	Language	Result	Execution time	Memory
720499		LittleCube	모임들 (IOI18_meetings)	C++14	17 / 100	120 ms	10032 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

namespace
{
  int N, Q;
  struct node
  {
    int L, R, sum, mid;
  } seg[400000];
  vector<int> H;
};

node merge(node n1, node n2)
{
  return node{max(n1.L, n1.sum + n2.L), max(n2.R, n2.sum + n1.R), n1.sum + n2.sum, max(max(n1.mid, n2.mid), n1.R + n2.L)};
}

void build(int i = 1, int L = 0, int R = N - 1)
{
  if (L == R)
  {
    int val = (H[L] == 1 ? 1 : -N);
    seg[i] = node{max(val, 0), max(val, 0), val, max(val, 0)};
  }
  else
  {
    int mid = (L + R) / 2;
    build(i << 1, L, mid);
    build(i << 1 | 1, mid + 1, R);
    seg[i] = merge(seg[i << 1], seg[i << 1 | 1]);
  }
}

node query(int qL, int qR, int i = 1, int L = 0, int R = N - 1)
{
  if (qL <= L && R <= qR)
    return seg[i];
  else if (R < qL || qR < L)
    return node{0, 0, 0, 0};
  else
  {
    int mid = (L + R) / 2;
    return merge(query(qL, qR, i << 1, L, mid), query(qL, qR, i << 1 | 1, mid + 1, R));
  }
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
  N = H.size(), Q = L.size();
  ::H = H;
  vector<ll> C(Q);
  build();
  for (int i = 0; i < Q; i++)
  {
    //cerr << query(L[i], R[i]).L << ' ' << query(L[i], R[i]).R << ' ' << query(L[i], R[i]).mid << ' ' << query(L[i], R[i]).sum << '\n';
    C[i] = (R[i] - L[i] + 1) * 2 - query(L[i], R[i]).mid;
  }
  return C;
}

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