제출 #97161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97161		MrTEK	새로운 문제 (POI11_pio)	C++14	54 / 100	1072 ms	47616 KiB

pio

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10