Submission #799646

#	Time	Username	Problem	Language	Result	Execution time	Memory
799646		erray	Holiday (IOI14_holiday)	C++17	100 / 100	233 ms	5604 KiB

holiday

#include"holiday.h"

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "/home/ioi/codes/ioi14_d2/debug.h"
#else 
  #define debug(...) void(37)
#endif
  
template<typename T> 
vector<T> inverse_fuck(T* a, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = a[i];
  }
  return res;
}

struct Fenwick {
  vector<int> ct;
  vector<long long> sum;
  int n;
  Fenwick(int _n) : n(_n) {
    ct.resize(n + 1);
    sum.resize(n + 1);
  }
  void modify(int x, long long d) {
    x += 1;
    while (x <= n) {
      sum[x] += d;
      ct[x] += (d < 0 ? -1 : 1);
      x += x & -x;
    }
  }
  long long get(int x) {
    long long res = 0, i = 0;
    for (int l = 1 << __lg(n); l > 0; l >>= 1) {
      if (i + l <= n && ct[i + l] <= x) {
        i += l;
        x -= ct[i];
        res += sum[i];
      }
    }
    return res;
  }
};

long long int findMaxAttraction(int N, int S, int D, int attraction[]) {
  auto A = inverse_fuck(attraction, N);  
  vector<int> comp(N);
  vector<int> ord(N);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int x, int y) {
    return A[x] > A[y];
  });
  for (int i = 0; i < N; ++i) {
    comp[ord[i]] = i;
  }
  auto Solve = [&] {
    vector<array<int, 4>> ranges;
    ranges.push_back({0, S, S, N - 1});
    long long res = 0;
    while (!ranges.empty()) {
      Fenwick fenw(N);
      int cl = 0, cr = -1;
      auto Get = [&](int l, int r) {
        assert(cl <= l && cr <= r && l <= S && S <= r);
        while (cr < r) {
          ++cr;
          debug(cr, comp[cr], A[cr]);
          fenw.modify(comp[cr], A[cr]);
        }
        while (cl < l) {
          fenw.modify(comp[cl], -A[cl]);
          ++cl;
        }
        return fenw.get(D - r - S + 2 * l);
      };
      vector<array<int, 4>> new_ranges;
      debug(ranges);
      for (auto[l, r, opt_l, opt_r] : ranges) {
        int mid = (l + r) >> 1;
        int opt = -1;
        long long mx = -1;
        for (int i = opt_l; i <= opt_r; ++i) {
          long long val = Get(mid, i);
          if (val > mx) {
            mx = val;
            opt = i;
          }
        } 
        res = max(res, mx);
        if (l < mid) {
          new_ranges.push_back({l, mid - 1, opt_l, opt});
        }
        if (mid < r) {
          new_ranges.push_back({mid + 1, r, opt, opt_r});
        }
      }
      swap(ranges, new_ranges);
    }
    return res;
  };
  long long ans = Solve();
  reverse(A.begin(), A.end());
  reverse(comp.begin(), comp.end());
  S = N - 1 - S;
  ans = max(ans, Solve());
  return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53