oj.uz

답안 #856583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856583 2023-10-04T02:27:59 Z fanwen 휴가 (IOI14_holiday) C++17
100 / 100
 191 ms 44264 KB 
#include <bits/stdc++.h>

#include "holiday.h"

using namespace std;

const int MAXN = 1e5 + 5;

int n, d, start, a[MAXN], root[MAXN];

long long ans = 0;
vector <int> cmp;

struct node_t {
    int le, ri, cnt = 0;
    long long sum = 0;
} it[18 * MAXN];

int Time;

void update(int pre, int nxt, int l, int r, int u, int val) {

    if(l > u || r < u || l > r) return;
    if(l == r) {
        it[nxt].sum = it[pre].sum + 1LL * val * cmp[l - 1];
        it[nxt].cnt = it[pre].cnt + val;
        return;
    }

    int mid = l + r >> 1;

    if(u <= mid) {
        it[nxt].ri = it[pre].ri;
        it[nxt].le = ++Time;
        update(it[pre].le, it[nxt].le, l, mid, u, val);
    } else {
        it[nxt].le = it[pre].le;
        it[nxt].ri = ++Time;
        update(it[pre].ri, it[nxt].ri, mid + 1, r, u, val);
    }

    it[nxt].cnt = it[it[nxt].le].cnt + it[it[nxt].ri].cnt;
    it[nxt].sum = it[it[nxt].le].sum + it[it[nxt].ri].sum;
}

long long getMax(int pre, int nxt, int l, int r, int cnt) {
    if(cnt <= 0) return 0;
    if(l == r) return 1LL * cnt * cmp[l - 1];

    int mid = l + r >> 1;

    int tmp = it[it[nxt].ri].cnt - it[it[pre].ri].cnt; 
    if(cnt <= tmp) return getMax(it[pre].ri, it[nxt].ri, mid + 1, r, cnt);
    long long ans = it[it[nxt].ri].sum - it[it[pre].ri].sum;
    ans += getMax(it[pre].le, it[nxt].le, l, mid, cnt - tmp);
    return ans;
}

void divide_and_conquer(int l, int r, int u, int v) {
    if(l > r) return;
    int mid = l + r >> 1;
    long long cost = -1;
    int p = u;
    for (int i = u; i <= v; ++i) {
        int L = start - mid, R = i - start, cnt = d - L - R - min(L, R);
        cnt = min(cnt, i - mid + 1);
        if(cnt < 0) continue;
        long long tmp = getMax(root[mid - 1], root[i], 1, n, cnt);
        if(cost < tmp) {
            cost = tmp;
            p = i;
        }
    }
    ans = max(ans, cost);
    divide_and_conquer(l, mid - 1, u, p);
    divide_and_conquer(mid + 1, r, p, v);
}

long long findMaxAttraction(int _n, int _start, int _d, int A[]) {
    ans = Time = 0;
    n = _n, d = _d, start = _start + 1;
    for (int i = 1; i <= n; ++i) a[i] = A[i - 1];
    cmp = vector <int> (a + 1, a + n + 1);
    sort(cmp.begin(), cmp.end()); cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin() + 1;
    }

    for (int i = 1; i <= n; ++i) {
        root[i] = ++Time;
        update(root[i - 1], root[i], 1, n, a[i], 1);
    }

    divide_and_conquer(1, start, start, n);
    return ans;
}
  
// Dream it. Wish it. Do it.

Compilation message

holiday.cpp: In function 'void update(int, int, int, int, int, int)':
holiday.cpp:30:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'long long int getMax(int, int, int, int, int)':
holiday.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'void divide_and_conquer(int, int, int, int)':
holiday.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 44124 KB Output is correct
2 Correct 30 ms 44124 KB Output is correct
3 Correct 30 ms 44124 KB Output is correct
4 Correct 31 ms 44124 KB Output is correct
5 Correct 35 ms 44124 KB Output is correct
6 Correct 14 ms 43356 KB Output is correct
7 Correct 22 ms 43608 KB Output is correct
8 Correct 25 ms 43600 KB Output is correct
9 Correct 12 ms 43096 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 43116 KB Output is correct
2 Correct 7 ms 43352 KB Output is correct
3 Correct 7 ms 43096 KB Output is correct
4 Correct 8 ms 43100 KB Output is correct
5 Correct 8 ms 43100 KB Output is correct
6 Correct 7 ms 43100 KB Output is correct
7 Correct 7 ms 43104 KB Output is correct
8 Correct 7 ms 43100 KB Output is correct
9 Correct 6 ms 43100 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 44192 KB Output is correct
2 Correct 45 ms 44236 KB Output is correct
3 Correct 39 ms 43612 KB Output is correct
4 Correct 8 ms 43100 KB Output is correct
5 Correct 7 ms 43100 KB Output is correct
6 Correct 6 ms 42868 KB Output is correct
7 Correct 6 ms 43096 KB Output is correct
8 Correct 191 ms 44264 KB Output is correct
9 Correct 154 ms 44256 KB Output is correct