Submission #40945

#	Time	Username	Problem	Language	Result	Execution time	Memory
40945		wzy	Lightning Conductor (POI11_pio)	C++11	100 / 100	188 ms	57664 KiB

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 (stderr)

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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10