Submission #582811

#	Time	Username	Problem	Language	Result	Execution time	Memory
582811		Vanilla	Meetings (IOI18_meetings)	C++17	36 / 100	789 ms	196692 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long int64;
const int maxn = 1e5 + 2;
const int lg = 20;

const int maxn_b = 5e3 + 2;
const int lg_b = 13;
int sparse[maxn_b][lg_b];
int64 dynam[maxn_b][maxn_b];
 
int qrrr (int l, int r) {
  int k = log2(r - l + 1);
  return max(sparse[l][k], sparse[r - (1 << k) + 1][k]);
}
 
vector<int64> minimum_costs_brute(vector<int> H, vector<int> L,
                                     vector<int> R) {
  int Q = L.size();
  int n = H.size();
  vector<int64> C(Q);
  for (int i = 1; i <= n; i++) {
    sparse[i][0] = H[i - 1];
  }
  for (int k = 1; k < lg; k++){
    for (int i = 1; i + (1 << k) - 1 <= n; i++){
      sparse[i][k] = max(sparse[i][k-1], sparse[i + (1 << (k - 1))][k-1]);
    }
  }
  for (int i = 1; i <= n; i++){ // dynam[l][r] -> suma toate qrrr(l, l <= i <= r)
    dynam[i][i] = H[i - 1];
    for (int j = i + 1; j <= n; j++){
      dynam[i][j] = dynam[i][j-1] + qrrr(i, j);
    }
  }
  for (int i = n; i >= 1; i--){ // dynam[r][l] -> suma toate qrrr(l <= i <= r, r)
    for (int j = i - 1; j >= 1; j--){
      dynam[i][j] = dynam[i][j + 1] + qrrr(j, i);
    }
  }
  for (int i = 0; i < Q; i++){
    L[i]++;
    R[i]++;
    int64 ans = min(dynam[L[i]][R[i]], dynam[R[i]][L[i]]);
    for (int j = L[i]; j < R[i]; j++){
      ans = min(ans, dynam[j][L[i]] + dynam[j + 1][R[i]]);
    }
    C[i] = ans;
  }
 
  return C;
}
int sp[maxn][lg];
int dp[maxn];
vector <pair <int, int> > inv;

int query (int l, int r) {
  int k = log2(r - l + 1);
  return max(sp[l][k], sp[r - (1 << k) + 1][k]);
}

vector<int64> minimum_costs(vector<int> H, vector<int> L,
                                     vector<int> R) {
  
  int Q = L.size();
  int n = H.size();
  if (Q <= 5000 && n <= 5000) return minimum_costs_brute(H, L, R);
  vector<int64> C(Q);
  int pt = -1;
  for (int i = 0; i < n; i++){
    if (H[i] == 2){
      if (pt != -1){
        inv.push_back({pt, i - 1});
        pt = -1;
      }
    }
    else {
      if (pt == -1) pt = i;
    }
  }
  if (pt != -1) inv.push_back({pt, n - 1});
  int m = inv.size();
  for (int i = 0; i < m; i++){
    sp[i][0] = inv[i].second - inv[i].first + 1;
  }
  for (int k = 1; k < lg; k++){
    for (int i = 0; i + (1 << k) - 1 < m; i++){
      sp[i][k] = max(sp[i][k-1], sp[i + (1 << (k - 1))][k-1]);
    }
  }
  for (int i = 0; i < Q; i++){
    int mx = 0;
    int l = lower_bound(inv.begin(), inv.end(), make_pair(L[i], -1)) - inv.begin();
    int r = lower_bound(inv.begin(), inv.end(), make_pair(R[i] + 1, -1)) - inv.begin();
    // [l, r)
    if (l != 0) {
      mx = max(mx, min(R[i], inv[l-1].second) - max(L[i], inv[l-1].first) + 1);
    }
    if (r != 0) {
      mx = max(mx, min(R[i], inv[r - 1].second) - max(L[i], inv[r - 1].first) + 1);
    }
    if (r - 2 >= l && inv[l].second <= R[i] && inv[r-2].first >= L[i]) mx = max(mx, query(l, r - 2));
    C[i] = (R[i] - L[i] + 1) * 2 - mx;
  }
 
  return C;
}

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