oj.uz

답안 #40945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40945 2018-02-09T23:33:37 Z wzy Lightning Conductor (POI11_pio) C++11
100 / 100
 188 ms 57664 KB 
#include <stdio.h>
#include <vector>
#include <stdint.h>
#include <math.h>
#include <iostream>
#define int long long
#define eps (int) 1e9
#define pb push_back
using namespace std;
int n  , v[500003] , ans[500003];

struct line{
	int a , b;
	double value(int x){
		return sqrt(x + a)+b; 
	}
};
int ponteiro = 0;
vector<line> cht;
int intersect(line i, line j){
	int l =- (int) min(i.a , j.a) , r = (int) 1e9;
	while(l <= r){
		int mid = (l+r);
		mid = floor(mid / 2.00); 
		double curr = i.value(mid ) - j.value(mid  );
		if(curr > 0){
			l = mid + 1;
		}
		else r = mid - 1;
	}
	return l;
}
void add_line(line x){
	while(cht.size() && cht.back().value(-x.a) < x.b && cht.back().value((int) 1e9) < x.value((int) 1e9)) cht.pop_back(); 
	if(cht.size() && cht.back().value(-x.a) >= x.b && cht.back().value((int) 1e9) >= x.value((int) 1e9)) return; 
	while(cht.size() >= 2 && intersect(cht[(int)cht.size() - 1] ,  x) <= intersect(cht[(int) cht.size() - 2] , cht.back())) cht.pop_back();  
	cht.pb(x); 
}
int query(int x){
	ponteiro = min(ponteiro , (int)cht.size() - 1);
	for(int i = ponteiro ; i < (int) cht.size() - 1 ; i ++){
		if(cht[i].value(x) > cht[i+1].value(x)) break;
		ponteiro++;
	}
	return ceil(cht[ponteiro].value(x)*1.000);
}

int32_t main(){
	scanf("%lld" , &n);
	for(int i = 1 ; i<=n;i++) scanf("%lld" , &v[i]);
	for(int i = 1 ; i <= n;i++){
		add_line({-i ,v[i]});
		ans[i] = query(i);
	}
	cht.clear();
	ponteiro = 0;
	for(int i = n ; i >= 1 ; i--){
		add_line({i , v[i]});
		ans[i] = max(ans[i] , query(-i));
	}
	for(int i = 1 ; i <= n;i++){
		printf("%lld\n" , ans[i] - v[i]); 
	}
}

Compilation message

pio.cpp: In function 'int32_t main()':
pio.cpp:49:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &n);
                    ^
pio.cpp:50:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1 ; i<=n;i++) scanf("%lld" , &v[i]);
                                                 ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 484 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 600 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1588 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 2712 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3432 KB Output is correct
2 Correct 21 ms 3544 KB Output is correct
3 Correct 24 ms 4192 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 5532 KB Output is correct
2 Correct 46 ms 6456 KB Output is correct
3 Correct 35 ms 7672 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 11972 KB Output is correct
2 Correct 69 ms 13868 KB Output is correct
3 Correct 73 ms 15800 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 22908 KB Output is correct
2 Correct 108 ms 24352 KB Output is correct
3 Correct 119 ms 28496 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 37096 KB Output is correct
2 Correct 141 ms 39000 KB Output is correct
3 Correct 165 ms 44944 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 47248 KB Output is correct
2 Correct 143 ms 51680 KB Output is correct
3 Correct 162 ms 57664 KB Output is correct