Submission #116582

#	Time	Username	Problem	Language	Result	Execution time	Memory
116582		mirbek01	Meetings (IOI18_meetings)	C++11	36 / 100	740 ms	196348 KiB

meetings

# include <bits/stdc++.h>
# include "meetings.h"

using namespace std;

const int N = 8e5 + 2;
const int M = 5e3 + 2;

long long a[M][M], t[N * 4];

void upd(int pos, int val, int v = 1, int tl = 1, int tr = N - 1){
      if(tl == tr)
            t[v] = val;
      else {
            int tm = (tl + tr) >> 1;
            if(pos <= tm)
                  upd(pos, val, v << 1, tl, tm);
            else
                  upd(pos, val, v << 1 | 1, tm + 1, tr);
            t[v] = max(t[v << 1], t[v << 1 | 1]);
      }
}

int get(int l, int r, int v = 1, int tl = 1, int tr = N - 1){
      if(l > tr || tl > r)
            return 0;
      if(l <= tl && tr <= r)
            return t[v];
      int tm = (tl + tr) >> 1;
      return max(get(l, r, v << 1, tl, tm),
                  get(l, r, v << 1 | 1, tm + 1, tr));
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
      int Q = L.size();
      int n = H.size();
      vector<long long> C(Q);
      if(n <= 5000){
            for(int i = 0; i < n; i ++){
                  a[i][i] = H[i];
                  for(int j = i - 1; j >= 0; j --)
                        a[i][j] = max(int(a[i][j + 1]), H[j]);
                  for(int j = i + 1; j < n; j ++)
                        a[i][j] = max(int(a[i][j - 1]), H[j]);
                  for(int j = 1; j < n; j ++)
                        a[i][j] += a[i][j - 1];
            }
            for(int i = 0; i < Q; i ++){
                  long long ret = 5e18;
                  for(int j = L[i]; j <= R[i]; j ++){
                        long long now = a[j][R[i]];
                        if(L[i])
                              now -= a[j][L[i] - 1];
                        ret = min(ret, now);
                  }
                  C[i] = ret;
            }
      } else {
            vector < pair <int, int> > qe;
            qe.push_back({-1, -1});
            int q = 0;
            for(int i = 0; i < n; i ++){
                  if(H[i] == 2)
                        continue;
                  int j = i;
                  while(j + 1 < n && H[j + 1] == 1)
                        j ++;
                  qe.push_back({i, j});
                  upd(++ q, j - i + 1);
                  i = j;
            }

            for(int i = 0; i < Q; i ++){
                  C[i] = (R[i] - L[i] + 1) * 2;
                  int mx = 0;
                  int lo = 1, hi = q;
                  while(hi - lo > 1){
                        int md = (lo + hi) >> 1;
                        if(qe[md].second >= L[i])
                              hi = md;
                        else
                              lo = md;
                  }
                  if(qe[lo].second >= L[i])
                        hi = lo;
                  if(qe[hi].second >= L[i] && qe[hi].first <= L[i]){
                        mx = min(qe[hi].second, R[i]) - L[i] + 1;
                  }
                  lo = 1, hi = q;
                  while(hi - lo > 1){
                        int md = (lo + hi) >> 1;
                        if(qe[md].first <= R[i])
                              lo = md;
                        else
                              hi = md;
                  }
                  if(qe[hi].first <= R[i])
                        lo = hi;
                  if(qe[lo].first <= R[i] && R[i] <= qe[lo].second)
                        mx = max(mx, R[i] - max(qe[lo].first, L[i]) + 1);
                  int l, r;
                  lo = 1, hi = q;
                  while(hi - lo > 1){
                        int md = (lo + hi) >> 1;
                        if(qe[md].first >= L[i])
                              hi = md;
                        else
                              lo = md;
                  }
                  if(qe[lo].first >= L[i])
                        hi = lo;
                  if(qe[hi].first < L[i])
                        hi ++;
                  l = hi;
                  lo = 1, hi = q;
                  while(hi - lo > 1){
                        int md = (lo + hi) >> 1;
                        if(qe[md].second <= R[i])
                              lo = md;
                        else
                              hi = md;
                  }
                  if(qe[hi].second <= R[i])
                        lo = hi;
                  if(qe[lo].second > R[i])
                        lo --;
                  r = lo;
                  if(l <= r && 1 <= l && r <= q)
                        mx = max(mx, get(l, r));
                  C[i] -= mx;
            }
      }
      return C;
}

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