Submission #40945

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
40945	2018-02-09T23:33:37 Z	wzy	Lightning Conductor (POI11_pio)	C++11	100 / 100	188 ms	57664 KB

pio

#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

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	248 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	484 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	600 KB	Output is correct

Subtask #4

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	1588 KB	Output is correct

Subtask #5

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	2712 KB	Output is correct

Subtask #6

9.0 / 9.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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