Submission #84881

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
84881	2018-11-17T16:46:40 Z	nikolapesic2802	Lightning Conductor (POI11_pio)	C++14	100 / 100	152 ms	15388 KB

pio

#include <bits/stdc++.h>
using namespace std;

const int mxN=5e5;
int n, h[mxN], a1[mxN], a2[mxN], sr[1000001], qu[mxN];

double ix(int i, int j) {
	double a=(j-i)/2.0/(h[j]-h[i])-(h[j]-h[i])/2.0;
	return a*a+j;
}

void solve(int a[mxN]) {
	for(int i=0, qh=0, qt=0; i<n; ++i) {
		if(!i||h[qu[qt-1]]<h[i]) {
			while(qt>qh&&h[i]>=h[qu[qt-1]]+sr[i-qu[qt-1]]||qt-qh>1&&ix(qu[qt-2], qu[qt-1])>ix(qu[qt-1], i))
				--qt;
			qu[qt++]=i;
		}
		while(qt-qh>1&&i>ix(qu[qh], qu[qh+1]))
			++qh;
		a[i]=h[qu[qh]]+sr[i-qu[qh]];
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	for(int i=1; i<=1000; ++i)
		for(int j=(i-1)*(i-1)+1; j<=i*i; ++j)
			sr[j]=i;
	cin >> n;
	for(int i=0; i<n; ++i)
		cin >> h[i];
	solve(a1);
	for(int i=0; i<n-1-i; ++i)
		swap(h[i], h[n-1-i]);
	solve(a2);
	for(int i=0; i<n; ++i)
		cout << max(a1[i], a2[n-1-i])-h[n-1-i] << "\n";
}

Compilation message

pio.cpp: In function 'void solve(int*)':
pio.cpp:15:15: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    while(qt>qh&&h[i]>=h[qu[qt-1]]+sr[i-qu[qt-1]]||qt-qh>1&&ix(qu[qt-2], qu[qt-1])>ix(qu[qt-1], i))
          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4216 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4340 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	4544 KB	Output is correct

Subtask #4

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	5104 KB	Output is correct

Subtask #5

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	5504 KB	Output is correct

Subtask #6

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	5648 KB	Output is correct
2	Correct	17 ms	5648 KB	Output is correct
3	Correct	24 ms	5784 KB	Output is correct

Subtask #7

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	6068 KB	Output is correct
2	Correct	31 ms	6068 KB	Output is correct
3	Correct	28 ms	6636 KB	Output is correct

Subtask #8

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	87 ms	8228 KB	Output is correct
2	Correct	54 ms	8228 KB	Output is correct
3	Correct	57 ms	8844 KB	Output is correct

Subtask #9

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	12008 KB	Output is correct
2	Correct	88 ms	12008 KB	Output is correct
3	Correct	85 ms	12044 KB	Output is correct

Subtask #10

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	15256 KB	Output is correct
2	Correct	120 ms	15256 KB	Output is correct
3	Correct	152 ms	15388 KB	Output is correct

Subtask #11

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	134 ms	15388 KB	Output is correct
2	Correct	122 ms	15388 KB	Output is correct
3	Correct	119 ms	15388 KB	Output is correct