oj.uz

답안 #799646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799646 2023-07-31T17:49:12 Z erray 휴가 (IOI14_holiday) C++17
100 / 100
 233 ms 5604 KB 
#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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 624 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 5560 KB Output is correct
2 Correct 68 ms 5568 KB Output is correct
3 Correct 64 ms 5552 KB Output is correct
4 Correct 68 ms 5604 KB Output is correct
5 Correct 90 ms 4716 KB Output is correct
6 Correct 22 ms 2132 KB Output is correct
7 Correct 43 ms 3316 KB Output is correct
8 Correct 53 ms 3736 KB Output is correct
9 Correct 15 ms 1492 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 5556 KB Output is correct
2 Correct 56 ms 5552 KB Output is correct
3 Correct 71 ms 2368 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 229 ms 4320 KB Output is correct
9 Correct 233 ms 4408 KB Output is correct