Submission #167479

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167479	2019-12-08T16:28:33 Z	Thuleanx	Lightning Conductor (POI11_pio)	C++14	100 / 100	166 ms	27988 KB

pio

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

const int N = 5e5+7;
int n;
int h[N];
int L[N], R[N];
double sqr[N];

struct Sol {
	int i, high;
	Sol(int i, int high):i(i), high(high) {}
	int value(int j) { return high + ceil(sqr[j-i]); }
	double actual_value(int j) { return high + sqr[j-i]; }
	int to(Sol &other) {
		int lo = other.i, hi = n-1;
		while (lo <= hi) {
			int mid = lo+hi>>1;	
			if (actual_value(mid) >= other.actual_value(mid)) 	lo = mid+1;
			else												hi = mid-1;
		}
		return lo;
	}
};

void solve(int A[]) {
	deque<Sol> dq;
	int hi = -1;
	for (int i = 0; i < n; i++) {
		while (dq.size() >= 2 && dq[0].to(dq[1]) <= i)
			dq.pop_front();
		if (dq.size())
			A[i] = dq.front().value(i);
		if (hi < h[i]) {
			Sol sol(i, h[i]);
			while (dq.size() && dq.back().to(sol) <= i)
				dq.pop_back();
			while (dq.size() >= 2 && dq[dq.size()-2].to(dq.back()) >= dq.back().to(sol))
				dq.pop_back();
			dq.push_back(sol);
		}
		hi = max(hi, h[i]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n;
	for (int i = 0; i < N; i++)
		sqr[i] = sqrt(i);
	for (int i = 0; i < n; i++)
		cin>>h[i];

	solve(L);
	reverse(h, h+n);
	solve(R);
	reverse(h, h+n);
	reverse(R, R+n);

	stringstream ss;
	for (int i = 0; i < n; i++) 
		ss << max(0, max(L[i],R[i])-h[i]) << endl;
	cout << ss.str();

	return 0;
}

Compilation message

pio.cpp: In member function 'int Sol::to(Sol&)':
pio.cpp:18:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo+hi>>1; 
              ~~^~~

Subtask #1

9.0 / 9.0

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

Subtask #2

9.0 / 9.0

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

Subtask #3

9.0 / 9.0

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

Subtask #4

9.0 / 9.0

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

Subtask #5

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	6540 KB	Output is correct

Subtask #6

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	6108 KB	Output is correct
2	Correct	21 ms	6108 KB	Output is correct
3	Correct	29 ms	7128 KB	Output is correct

Subtask #7

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	6892 KB	Output is correct
2	Correct	33 ms	7640 KB	Output is correct
3	Correct	39 ms	9068 KB	Output is correct

Subtask #8

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	10400 KB	Output is correct
2	Correct	63 ms	11888 KB	Output is correct
3	Correct	79 ms	13172 KB	Output is correct

Subtask #9

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	107 ms	18876 KB	Output is correct
2	Correct	95 ms	12672 KB	Output is correct
3	Correct	118 ms	19008 KB	Output is correct

Subtask #10

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	151 ms	24984 KB	Output is correct
2	Correct	132 ms	16216 KB	Output is correct
3	Correct	162 ms	25044 KB	Output is correct

Subtask #11

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	166 ms	17768 KB	Output is correct
2	Correct	128 ms	21096 KB	Output is correct
3	Correct	164 ms	27988 KB	Output is correct