#include #include #include using namespace std; using ll = long long; //vector position을 int meeting_position으로 바꾸고 매개변수 넘겨 줄때 position[idx]할까? ll calculate_meeting_cost(const vector& position, const vector& posistion_prefix_sum, int l, int r, int idx) { return (ll)(2 * idx - l - r) * position[idx] - (posistion_prefix_sum[idx] - posistion_prefix_sum[l - 1]) + (posistion_prefix_sum[r] - posistion_prefix_sum[idx - 1]); } ll calculate_min_fatigue(const vector& position, const vector& position_prefix_sum, int l, int r) { int first = lower_bound(position.begin(), position.end(), l) - position.begin(); int last = upper_bound(position.begin(), position.end(), r) - position.begin() - 1; if (first >= last) { return 0; } int mid = (first + last) / 2; ll foo = (last - first + 1) * (position[mid] - position[first]) - 2 * ((mid - first + 1) * position[mid] - (position_prefix_sum[mid] - position_prefix_sum[first - 1])); ll bar = (last - first + 1) * (position[last] - position[mid]) - 2 * ((last - mid + 1) * position[last] - (position_prefix_sum[last] - position_prefix_sum[mid - 1])); //ll foo = (mid - first + 1) * position[last] - (position_prefix_sum[mid] - position_prefix_sum[first - 1]); //- (position_prefix_sum[last] - position_prefix_sum[mid] - (last - mid) * position[mid]); //ll bar = (last - mid + 1) * position[first] - (position_prefix_sum[last] - position_prefix_sum[mid - 1]) //- (position_prefix_sum[mid] - position_prefix_sum[first] - (mid - first) * position[first]); return max(foo, bar); ll cost_at_first = calculate_meeting_cost(position, position_prefix_sum, first, last, first); ll cost_at_last = calculate_meeting_cost(position, position_prefix_sum, first, last, last); ll max_cost = max(cost_at_first, cost_at_last); ll min_cost = calculate_meeting_cost(position, position_prefix_sum, first, last, (first + last) / 2); return max_cost - min_cost; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector position(n + 1); vector position_prefix_sum(n + 1); for (int i = 1; i <= n; ++i) { cin >> position[i]; position_prefix_sum[i] = position_prefix_sum[i - 1] + position[i];//이거 여기서 처리하는 거 srp위반? } while (q--) { int l, r; cin >> l >> r; cout << calculate_min_fatigue(position, position_prefix_sum, l, r) << '\n'; } return 0; }

제출 #155756

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: