oj.uz

답안 #298004

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
298004 2020-09-12T09:28:27 Z MoNsTeR_CuBe 모임들 (IOI18_meetings) C++17
4 / 100
 5500 ms 1792 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long




#undef int
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) {
  #define int long long
  int q = L.size();
  int n = H.size();
  vector< int > firstLeft(n,-1);
  vector< int > firstRight(n,numeric_limits<int>::max());
  
  vector< pair<int,int> > stack;
  
  for(int i = n-1; i >= 0; i--){
	while(!stack.empty() && stack.back().first < H[i]){
		stack.pop_back();
	}
	if(!stack.empty()){
		firstRight[i] = stack.back().second;
	}
	stack.push_back({H[i],i});
  }
  
  stack.clear();
  
  for(int i = 0; i < n; i++){
	while(!stack.empty() && stack.back().first < H[i]){
		stack.pop_back();
	}
	if(!stack.empty()){
		firstLeft[i] = stack.back().second;
	}
	stack.push_back({H[i],i});
  }
  
  vector< int > ans(q);
  
  for(int i = 0; i < q; i++){
	int best = numeric_limits<int>::max();
	
	for(int j = L[i]; j <= R[i]; j++){
		int tot = -H[j]; //AVOID COUNTING TWICE
		int currLeft = j;
		int currRight = j;
		int currCost = H[j];
		
		while(firstLeft[currLeft] >= L[i]){
			tot += (currLeft-firstLeft[currLeft])*currCost;
			currLeft = firstLeft[currLeft];
			currCost = H[currLeft];
		}
		tot += (currLeft-L[i]+1)*currCost;
		currCost = H[j];
		
		//cout << "LEFT " << tot << endl;
		
		while(firstRight[currRight] <= R[i]){
			//cout << "RIGHTE " << firstRight[currRight] << ' ' << currRight << endl;
			tot += (firstRight[currRight]-currRight)*currCost;
			currRight = firstRight[currRight];
			currCost = H[currRight];
			//cout << tot << endl;
		}
		tot += (R[i] - currRight+1)*currCost;
		if(tot < best){
			//cout << tot << ' ' << j << endl;
			best = tot;
		}
	}
	//cout << "done" << endl;
	ans[i] = best;
  }
  return ans;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 40 ms 384 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 40 ms 384 KB Output is correct
10 Correct 310 ms 760 KB Output is correct
11 Correct 1022 ms 760 KB Output is correct
12 Correct 323 ms 700 KB Output is correct
13 Correct 1426 ms 760 KB Output is correct
14 Execution timed out 5542 ms 896 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Execution timed out 5565 ms 1792 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Execution timed out 5565 ms 1792 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 40 ms 384 KB Output is correct
10 Correct 310 ms 760 KB Output is correct
11 Correct 1022 ms 760 KB Output is correct
12 Correct 323 ms 700 KB Output is correct
13 Correct 1426 ms 760 KB Output is correct
14 Execution timed out 5542 ms 896 KB Time limit exceeded
15 Halted 0 ms 0 KB -