oj.uz

Submission #29594

# Submission time Handle Problem Language Result Execution time Memory
29594 2017-07-20T07:46:40 Z 박상수(#1244) Lightning Conductor (POI11_pio) C++11
27 / 100
 196 ms 9832 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];

void Do1(int l, int r, int s, int d) {
	int m = (l + r) >> 1;
	int mi = -1, mx = -1;
	for(int i=s;i<=d&&i<=m;i++) {
		int t = h[i] + sq[m-i];
		if(mx < t) mx = t, mi = i;
	}
	ans[m] = max(ans[m], mx);
	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, mx = -1;
	for(int i=max(m,s);i<=d;i++) {
		int t = h[i] + sq[i-m];
		if(mx < t) mx = t, mi = i;
	}
	ans[m] = max(ans[m], mx);
	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;
	}
	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:67:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
pio.cpp:68: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
0 / 9.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9832 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 9832 KB Output is correct
2 Incorrect 129 ms 9832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 9832 KB Output is correct
2 Incorrect 173 ms 9832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

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