oj.uz

Submission #29596

# Submission time Handle Problem Language Result Execution time Memory
29596 2017-07-20T07:50:46 Z 박상수(#1244) Lightning Conductor (POI11_pio) C++11
100 / 100
 206 ms 17656 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;
typedef long double ldouble;

int sq[1000020];
int n, h[500050];
int ans[500050];
double sqf[1000020];

void Do1(int l, int r, int s, int d) {
	int m = (l + r) >> 1;
	double mxf = -1;
	int mi = -1;
	for(int i=s;i<=d&&i<=m;i++) {
		double tf = h[i] + sqf[m-i];
		if(mxf < tf) mxf = tf, mi = i;
	}
	ans[m] = max(ans[m], h[mi] + sq[m-mi]);
	if(l<m) Do1(l, m-1, s, mi);
	if(m<r) Do1(m+1, r, mi, d);
}

void Do2(int l, int r, int s, int d) {
	int m = (l + r) >> 1;
	int mi = -1;
	double mxf = -1;
	for(int i=max(m,s);i<=d;i++) {
		double tf = h[i] + sqf[i-m];
		if(mxf < tf) mxf = tf, mi = i;
	}
	ans[m] = max(ans[m], h[mi] + sq[mi-m]);
	if(l<m) Do2(l, m-1, s, mi);
	if(m<r) Do2(m+1, r, mi, d);
}

int main(){
	for(int i=1, j=1;i<=1000000;i++) {
		while(j*j<i)++j;
		sq[i] = j;
		sqf[i] = sqrt(i);
	}
	scanf("%d", &n);
	for(int i=1;i<=n;i++) scanf("%d", h+i);
	
	Do1(1, n, 1, n);
	
	Do2(1, n, 1, n);
	for(int i=1;i<=n;i++) printf("%d\n", ans[i] - h[i]);
	
	return 0;
}

Compilation message

pio.cpp: In function 'int main()':
pio.cpp:71:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
pio.cpp:72:40: 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("%d", h+i);
                                        ^

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17656 KB Output is correct

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17656 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 17656 KB Output is correct
2 Correct 23 ms 17656 KB Output is correct
3 Correct 33 ms 17656 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17656 KB Output is correct
2 Correct 43 ms 17656 KB Output is correct
3 Correct 39 ms 17656 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 17656 KB Output is correct
2 Correct 86 ms 17656 KB Output is correct
3 Correct 96 ms 17656 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 17656 KB Output is correct
2 Correct 183 ms 17656 KB Output is correct
3 Correct 146 ms 17656 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 17656 KB Output is correct
2 Correct 183 ms 17656 KB Output is correct
3 Correct 189 ms 17656 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 17656 KB Output is correct
2 Correct 206 ms 17656 KB Output is correct
3 Correct 183 ms 17656 KB Output is correct