oj.uz

Submission #97161

# Submission time Handle Problem Language Result Execution time Memory
97161 2019-02-14T08:01:30 Z MrTEK Lightning Conductor (POI11_pio) C++14
54 / 100
 1000 ms 47616 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 5e5 + 5;
const int LOG = 20;

int n,a[N],rmq[N][LOG];
short int logtwo[N];  

void build() {
  logtwo[0] = -1;
  for (int i = 1 ; i <= n ; i++) {
    rmq[i][0] = a[i];
    logtwo[i] = logtwo[i / 2] + 1;
  }
  for (int i = 1 ; i < LOG ; i++)
    for (int j = 1 ; j <= n ; j++)
      rmq[j][i] = max(rmq[j][i - 1],rmq[min(n,j + (1 << (i - 1)))][i - 1]);
}

int query (int l,int r) {
  l = max(l,1);
  r = min(r,n);
  if (l > r)
    return -1e8;
  int j = logtwo[r - l + 1];
  return max(rmq[l][j],rmq[r - (1 << j) + 1][j]);
}

int solve_left(int x) {
  int mx = sqrt(x - 1) + 1,lst = x,res = 0;
  for (int i = 1 ; i <= mx ; i++) {
    int l = x - i * i;
    res = max(res,query(l,lst - 1) - a[x] + i);
    lst = l;
  }
  return res;
}

int solve_right(int x) {
  int mx = sqrt(n - x) + 1,lst = x,res = 0;
  for (int i = 1 ; i <= mx ; i++) {
    int r = x + i * i;
    res = max(res,query(lst + 1,r) - a[x] + i);
    lst = r;
  }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n;
  for (int i = 1 ; i <= n ; i++)
    cin >> a[i];
  build();
  for (int i = 1 ; i <= n ; i++)
    cout << max(solve_left(i),solve_right(i)) << "\n";
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 3440 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 5508 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 6920 KB Output is correct
2 Correct 603 ms 6332 KB Output is correct
3 Correct 767 ms 6776 KB Output is correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1006 ms 9956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 22172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 33732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1045 ms 47616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 47524 KB Time limit exceeded
2 Halted 0 ms 0 KB -