oj.uz

답안 #167446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167446 2019-12-08T15:11:37 Z Thuleanx Lightning Conductor (POI11_pio) C++14
27 / 100
 146 ms 22948 KB 
#include <bits/stdc++.h>
using namespace std;

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

struct Sol {
	int i, high;
	Sol(int i, int high):i(i), high(high) {}
	int 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 (value(mid) <= other.value(mid))
				lo = mid+1;
			else
				hi = mid-1;
		}
		return lo;
	}
};

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

	cin>>n;
	memset(L,0,sizeof(L)); 
	memset(R,0,sizeof(R));
	memset(sqr,0,sizeof(sqr));
	for (int i = 0; i*i+1 < N; i++) 
		sqr[i*i+1] = i+1;
	for (int i = 1; i < N; i++)
		sqr[i] = max(sqr[i], sqr[i-1]);

	deque<Sol> dq;
	// forward
	for (int i = 0; i < n; i++) {
		cin>>h[i];
		while (dq.size() >= 2 && dq[dq.size()-2].value(i) > dq.back().value(i))
			dq.pop_back();
		if (dq.size())
			L[i] = dq.back().value(i);
		Sol sol(i, h[i]);
		if (dq.size() && dq.back().value(i) >= h[i]) continue;
		while (dq.size() >= 2 && dq[dq.size()-2].to(dq.back()) <= dq.back().to(sol))
			dq.pop_back();
		dq.push_back(sol);
	}
	// backward
	reverse(h, h+n);
	dq.clear();
	for (int i = 0; i < n; i++) {
		while (dq.size() >= 2 && dq[dq.size()-2].value(i) > dq.back().value(i))
			dq.pop_back();
		if (dq.size())
			R[i] = dq.back().value(i);
		Sol sol(i, h[i]);
		if (dq.size() && dq.back().value(i) >= h[i]) continue;
		while (dq.size() >= 2 && dq[dq.size()-2].to(dq.back()) <= dq.back().to(sol))
			dq.pop_back();
		dq.push_back(sol);
	}
	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:17:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo+hi>>1; 
              ~~^~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 6392 KB Output isn't correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6264 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 6264 KB Output isn't correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 7288 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 8052 KB Output is correct

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 7540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 8052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 10472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 18100 KB Output is correct
2 Correct 92 ms 12016 KB Output is correct
3 Incorrect 92 ms 18148 KB Output isn't correct

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 22948 KB Output is correct
2 Incorrect 126 ms 14184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 135 ms 15892 KB Output isn't correct
2 Halted 0 ms 0 KB -