oj.uz

답안 #613982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613982 2022-07-30T15:33:16 Z 1ne 모임들 (IOI18_meetings) C++14
0 / 100
 228 ms 1884 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<long long> minimum_costs(std::vector<int> arr, std::vector<int> L,
                                     std::vector<int> R) {
  int m = (int)L.size();
  int n = (int)arr.size(); 
  vector<long long>ans(m);
  vector<long long>pref(n + 1),suff(n + 1);
  priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>>q;
  vector<long long>pref_cnt(n + 1,0),suff_cnt(n + 1,0);
  for (long long i = 0;i < n;++i){
	  pref[i + 1] = pref[i] + arr[i];
	  long long counts = 1;
	  while(!q.empty() && q.top().first < arr[i]){
			pref[i + 1] += (arr[i] - q.top().first)*q.top().second;
			pref_cnt[i + 1] +=(arr[i] - q.top().first) * q.top().second;
			counts+=q.top().second;
			q.pop();
	  }  
	  q.push({arr[i],counts});
  }
  while(!q.empty())q.pop();
  for (long long i = n - 1;i>=0;--i){
		suff[i] = suff[i + 1] + arr[i];
		long long counts = 1;
		while(!q.empty() && q.top().first < arr[i]){
			suff[i]+=(arr[i] - q.top().first) * q.top().second;	
			suff_cnt[i]+=(arr[i] - q.top().first) * q.top().second;
			counts+=q.top().second;
			q.pop();
		}
		q.push({arr[i],counts});
  }
  for (long long i = 1;i<=n;++i){
		pref_cnt[i] +=pref_cnt[i - 1];
  }
  for (long long i = n - 1;i>=0;--i){
		suff_cnt[i] +=suff_cnt[i + 1];
  }
  for (long long i = 0;i<m;++i){
	  long long answer = LLONG_MAX;
	  for (long long j = L[i];j<=R[i];++j){
		 //cout<<i<<" "<<pref[j]<<" "<<suff[j]<<'\n';
		 answer = min(answer,pref[j + 1] + suff[j] - arr[j] - pref[L[i]] - suff[R[i] + 1] - pref_cnt[L[i] + 1] - suff_cnt[R[i] + 1]);
	  }
	  ans[i] = answer;
  }
  return ans;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 228 ms 1884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 228 ms 1884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -