oj.uz

Submission #81841

# Submission time Handle Problem Language Result Execution time Memory
81841 2018-10-27T07:40:25 Z tmwilliamlin168 Lightning Conductor (POI11_pio) C++14
18 / 100
 129 ms 23104 KB 
#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]) {
	int qh=0, qt=0;
	for(int i=0; i<n; ++i) {
		if(!i||h[qu[qt-1]]<h[i]) {
			while(qt-qh>1&&h[i]>=h[qu[qt-1]]+sr[i-qu[qt-1]]||ix(qu[qt-2], qu[qt-1])>ix(qu[qt-1], i))
				--qt;
			qu[qt++]=i;
		}
		while(qt-qh>1&&h[qu[qh+1]]+sr[i-qu[qh+1]]>h[qu[qh]]+sr[i-qu[qh]])
			++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:16:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    while(qt-qh>1&&h[i]>=h[qu[qt-1]]+sr[i-qu[qt-1]]||ix(qu[qt-2], qu[qt-1])>ix(qu[qt-1], i))
          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4344 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4348 KB Output isn't correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4348 KB Output isn't correct

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5684 KB Output is correct
2 Correct 17 ms 5684 KB Output is correct
3 Incorrect 18 ms 5760 KB Output isn't correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 6144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8320 KB Output is correct
2 Correct 64 ms 8320 KB Output is correct
3 Incorrect 50 ms 8848 KB Output isn't correct

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 12080 KB Output is correct
2 Correct 82 ms 12080 KB Output is correct
3 Incorrect 78 ms 12080 KB Output isn't correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 15248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 15248 KB Output is correct
2 Correct 116 ms 17312 KB Output is correct
3 Incorrect 108 ms 23104 KB Output isn't correct