oj.uz

답안 #555612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
555612 2022-05-01T09:19:10 Z MilosMilutinovic 휴가 (IOI14_holiday) C++14
100 / 100
 623 ms 13740 KB 
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 500000;

int n, s, a[MAX], cc[4 * MAX], ord[MAX], id[MAX], tl, tr;
long long sum[4 * MAX], dL[MAX], dl[MAX], dR[MAX], dr[MAX];

void modify(int node, int l, int r, int i, int x, int v) {
  cc[node] += x;
  sum[node] += v;
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    modify(node + node, l, mid, i, x, v);
  } else {
    modify(node + node + 1, mid + 1, r, i, x, v);
  }
}

long long walk(int node, int l, int r, int x) {
  if (l == r) {
    return (x >= 1 ? sum[node] : 0LL);
  }
  int mid = l + r >> 1;
  if (cc[node + node + 1] >= x) {
    return walk(node + node + 1, mid + 1, r, x);
  } else {
    return sum[node + node + 1] + walk(node + node, l, mid, x - cc[node + node + 1]);
  }
}

void fixL(int l) {
  while (tl > l) {
    --tl;
    modify(1, 0, n - 1, id[tl], 1, a[tl]);
  }
  while (tl < l) {
//    cout << "brisem " << tl << '\n';
    modify(1, 0, n - 1, id[tl], -1, -a[tl]);
    tl++;
  }
}

void fixR(int r) {
  while (tr < r) {
    tr++;
//    cout << "addujem " << tr << '\n';
    modify(1, 0, n - 1, id[tr], 1, a[tr]);
  }
  while (tr > r) {
    modify(1, 0, n - 1, id[tr], -1, -a[tr]);
    tr--;
  }
}

long long get(int L, int R, int x) {
  fixL(L);
  fixR(R);
  return walk(1, 0, n - 1, x);
}

void solveL(int l, int r, int ll, int rr, int dc, long long* c) {
  if (l > r) {
    return;
  }
  int mid = l + r >> 1;
  int opt = rr;
  long long mx = -1;
  for (int i = rr; i >= ll; i--) {
    if ((s - i) * dc > mid) {
      continue;
    }
    long long cur = get(i, s - (dc == 1), mid - (s - i) * dc);
    if (mx < cur) {
      mx = cur;
      opt = i;
    }
  }
  c[mid] = mx;
  solveL(l, mid - 1, opt, rr, dc, c);
  solveL(mid + 1, r, ll, opt, dc, c);
}

void solveR(int l, int r, int ll, int rr, int dc, long long* c) {
  if (l > r) {
    return;
  }
  int mid = l + r >> 1;
  int opt = ll;
  long long mx = -1;
  for (int i = ll; i <= rr; i++) {
    if ((i - s) * dc > mid) {
      continue;
    }
    long long cur = get(s + (dc == 1), i, mid - (i - s) * dc);
    if (mx < cur) {
      mx = cur;
      opt = i;
    }
  }
  c[mid] = mx;
  solveR(l, mid - 1, ll, opt, dc, c);
  solveR(mid + 1, r, opt, rr, dc, c);
}

long long findMaxAttraction(int N, int start, int d, int attraction[]) {
  n = N;
  s = start;
  for (int i = 0; i < n; i++) {
    a[i] = attraction[i];
    ord[i] = i;
  }
  sort(ord, ord + n, [&](int i, int j) {
    return a[i] < a[j];
  });
  for (int i = 0; i < n; i++) {
    id[ord[i]] = i;
  }
  tr = -1, tl = 0;
  solveL(0, d, 0, s, 2, dL);
  solveL(0, d, 0, s, 1, dl);
  solveR(0, d, s, n - 1, 2, dR);
  solveR(0, d, s, n - 1, 1, dr);
  long long ans = max(dl[d], dr[d]);
  for (int i = 0; i <= d; i++) {
    ans = max(ans, dL[i] + dr[d - i]);
    ans = max(ans, dl[i] + dR[d - i]);
  }
  return ans;
}

Compilation message

holiday.cpp: In function 'void modify(int, int, int, int, int, int)':
holiday.cpp:17:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |   int mid = l + r >> 1;
      |             ~~^~~
holiday.cpp: In function 'long long int walk(int, int, int, int)':
holiday.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid = l + r >> 1;
      |             ~~^~~
holiday.cpp: In function 'void solveL(int, int, int, int, int, long long int*)':
holiday.cpp:71:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |   int mid = l + r >> 1;
      |             ~~^~~
holiday.cpp: In function 'void solveR(int, int, int, int, int, long long int*)':
holiday.cpp:93:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 704 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 472 ms 11456 KB Output is correct
2 Correct 476 ms 11432 KB Output is correct
3 Correct 514 ms 11376 KB Output is correct
4 Correct 494 ms 11448 KB Output is correct
5 Correct 619 ms 9244 KB Output is correct
6 Correct 247 ms 7764 KB Output is correct
7 Correct 373 ms 5716 KB Output is correct
8 Correct 391 ms 5816 KB Output is correct
9 Correct 171 ms 9268 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 1108 KB Output is correct
2 Correct 11 ms 1092 KB Output is correct
3 Correct 13 ms 1108 KB Output is correct
4 Correct 12 ms 980 KB Output is correct
5 Correct 11 ms 980 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 700 KB Output is correct
8 Correct 3 ms 696 KB Output is correct
9 Correct 3 ms 704 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 623 ms 12976 KB Output is correct
2 Correct 555 ms 13740 KB Output is correct
3 Correct 114 ms 3440 KB Output is correct
4 Correct 9 ms 852 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 559 ms 7396 KB Output is correct
9 Correct 564 ms 7376 KB Output is correct