oj.uz

답안 #197461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197461 2020-01-21T12:02:59 Z DS007 휴가 (IOI14_holiday) C++14
100 / 100
 431 ms 64684 KB 
#include <bits/stdc++.h>
#include <holiday.h>
using namespace std;
 
#define tm (tl + tr) / 2
 
struct node {
    long long val;
    int size;
    int left, right;
 
    node() {
        val = size = 0;
        left = right = 0;
    }
} nodes[2000000];
 
const int NN = 1e5, DD = 2 * NN + NN / 2;
map<int, int> m1, m2;
int v[NN + 1];
int con = 0;
int N, START, D, *ATTRACTION;
long long dp1[DD + 1], dp2[DD + 1], dp3[DD + 1], dp4[DD + 1];
// int l1[DD + 1], l2[DD + 1], l3[DD + 1], l4[DD + 1];
 
void pre() {
    int copy[N];
    for (int i = 0; i < N; i++)
        copy[i] = ATTRACTION[i];
    sort(copy, copy + N);
 
    set<int> s;
    for (int i = 0, j = 0; i < N; i++) {
        if (s.count(copy[i]))
            continue;
        m1[copy[i]] = j;
        m2[j++] = copy[i];
    }
}
 
void update(int cur, int prev, int tl, int tr, int l) {
    if (l == tl && tl == tr) {
        nodes[cur].val = nodes[prev].val + m2[l];
        nodes[cur].size = nodes[prev].size + 1;
        return;
    }
 
    // int tm = (tl + tr) / 2;
    if (l <= tm) {
        nodes[cur].right = nodes[prev].right;
        nodes[cur].left = con++;
        update(nodes[cur].left, nodes[prev].left, tl, tm, l);
    } else {
        nodes[cur].left = nodes[prev].left;
        nodes[cur].right = con++;
        update(nodes[cur].right, nodes[prev].right, tm + 1, tr, l);
    }
 
    nodes[cur].val = nodes[nodes[cur].left].val + nodes[nodes[cur].right].val;
    nodes[cur].size = nodes[nodes[cur].left].size + nodes[nodes[cur].right].size;
}
 
void build(int n, int tl, int tr) {
    if (tl == tr)
        return;
 
    nodes[n].left = con++;
    nodes[n].right = con++;
    // int tm = (tl + tr) / 2;
    build(nodes[n].left, tl, tm);
    build(nodes[n].right, tm + 1, tr);
}
 
void build() {
    v[0] = con++;
    build(v[0], 0, N - 1);
 
    for (int i = 1; i <= N; i++) {
        v[i] = con++;
        update(v[i], v[i - 1], 0, N - 1, m1[ATTRACTION[i - 1]]);
    }
}
 
long long query(int n1, int n2, int tl, int tr, int c) {
    c = min(c, nodes[n2].size - nodes[n1].size);
    if (c <= 0)
        return 0;
 
    if (nodes[n2].size - nodes[n1].size == c)
        return nodes[n2].val - nodes[n1].val;
 
    if (tl == tr)
        return m2[tl] * c;
 
    // int tm = (tl + tr) / 2;
    
    if (nodes[nodes[n2].right].size - nodes[nodes[n1].right].size >= c)
        return query(nodes[n1].right, nodes[n2].right, tm + 1, tr, c);
    else
        return nodes[nodes[n2].right].val - nodes[nodes[n1].right].val + query(nodes[n1].left, nodes[n2].left, tl, tm, c - (nodes[nodes[n2].right].size - nodes[nodes[n1].right].size));
}
 
/*void calc1() {
    dp1[1] = dp1[2] = ATTRACTION[START];
    l1[1] = l1[2] = START;
 
    for (int i = 3; i <= D; i++) {
        int t = query(v[l1[i - 1]], v[START + 1], i - 2 * (START - l1[i - 1])), j = l1[i - 1] - 1;
        while (j >= 0) {
            int temp = query(v[j], v[START + 1], i - 2 * (START - j));
            if (temp < t)
                break;
            t = temp;
            j--;
        }
 
        dp1[i] = t;
        l1[i] = j == -1 ? 0 : j;
    }
}*/
 
void calc1() {
    pair<long long, int> best = {ATTRACTION[START], START};
    for (int i = START - 1; i >= 0; i--)
        best = max(best, {query(v[i], v[START + 1], 0, N - 1, D - 2 * (START - i)), i});
    dp1[D] = best.first;
    // l1[D] = best.second;
    int l = best.second;
 
    for (int i = D - 1; i >= 0; i--) {
        pair<long long, int> t = {query(v[l], v[START + 1], 0, N - 1, i - 2 * (START - l)), l};
        for (int j = l + 1; j <= START; j++) {
            pair<long long, int> temp = {query(v[j], v[START + 1], 0, N - 1, i - 2 * (START - j)), j};
            if (max(t, temp) == t)
                break;
            t = temp;
        }
        dp1[i] = t.first;
        l = t.second;
    }
}
 
/*void calc2() {
    dp2[1] = dp2[2] = ATTRACTION[START];
    l2[1] = l2[2] = START;
 
    for (int i = 3; i <= D; i++) {
        int t = query(v[START], v[l2[i - 1] + 1], i - 2 * (l1[i - 1] - START)), j = l1[i - 1] + 1;
        while (j < N) {
            int temp = query(v[START], v[j + 1], i - 2 * (j - START));
            if (temp < t)
                break;
            t = temp;
            j++;
        }
 
        dp2[i] = t;
        l2[i] = j == N ? N - 1 : j;
    }
}*/
 
void calc2() {
    pair<long long, int> best = {ATTRACTION[START], START};
    for (int i = START + 1; i < N; i++)
        best = max(best, {query(v[START], v[i + 1], 0, N - 1, D - 2 * (i - START)), i});
    dp2[D] = best.first;
    // l2[D] = best.second;
    int l = best.second;
 
    for (int i = D - 1; i >= 0; i--) {
        pair<long long, int> t = {query(v[START], v[l + 1], 0, N - 1, i - 2 * (l - START)), l};
        for (int j = l - 1; j >= START; j--) {
            pair<long long, int> temp = {query(v[START], v[j + 1], 0, N - 1, i - 2 * (j - START)), j};
            if (max(t, temp) == t)
                break;
            t = temp;
        }
        dp2[i] = t.first;
        l = t.second;
    }
}
 
/*void calc3() {
    dp3[1] = ATTRACTION[START + 1];
    l3[1] = START + 1;
 
    for (int i = 2; i <= D; i++) {
        int t = query(v[START + 1], v[l3[i - 1] + 1], i - (l3[i - 1] - START - 1)), j = l3[i - 1] + 1;
        while (j < N) {
            int temp = query(v[START + 1], v[j + 1], i - (j - START - 1));
            if (temp < t)
                break;
            t = temp;
            j++;
        }
 
        dp3[i] = t;
        l3[i] = j == N ? N - 1 : j;
    }
}*/
 
void calc3() {
    pair<long long, int> best = {ATTRACTION[START + 1], START + 1};
    for (int i = START + 2; i < N; i++)
        best = max(best, {query(v[START + 1], v[i + 1], 0, N - 1, D - (i - START - 1)), i});
    dp3[D] = best.first;
    // l3[D] = best.second;
    int l = best.second;
 
    for (int i = D - 1; i >= 0; i--) {
        pair<long long, int> t = {query(v[START + 1], v[l + 1], 0, N - 1, i - (l - START - 1)), l};
        for (int j = l - 1; j >= START + 1; j--) {
            pair<long long, int> temp = {query(v[START + 1], v[j + 1], 0, N - 1, i - (j - START - 1)), j};
            if (max(t, temp) == t)
                break;
            t = temp;
        }
        dp3[i] = t.first;
        l = t.second;
    }
}
 
/*void calc4() {
    dp4[1] = ATTRACTION[START - 1];
    l4[1] = START - 1;
 
    for (int i = 2; i <= D; i++) {
        int t = query(v[l4[i - 1]], v[START], i - (START - 1 - l4[i - 1])), j = l4[i - 1] - 1;
        while (j >= 0) {
            int temp = query(v[j], v[START], i - (START - 1 - j));
            if (temp < t)
                break;
 
        }
    }
}*/
 
void calc4() {
    pair<long long, int> best = {ATTRACTION[START - 1], START - 1};
    for (int i = START - 2; i >= 0; i--)
        best = max(best, {query(v[i], v[START], 0, N - 1, D - (START - 1 - i)), i});
    dp4[D] = best.first;
    // l4[D] = best.second;
    int l = best.second;
 
    for (int i = D - 1; i >= 0; i--) {
        pair<long long, int> t = {query(v[l], v[START], 0, N - 1, i - (START - 1 - l)), l};
        for (int j = l + 1; j <= START - 1; j++) {
            pair<long long, int> temp = {query(v[j], v[START], 0, N - 1, i - (START - 1 - j)), j};
            if (max(t, temp) == t)
                break;
            t = temp;
        }
        dp4[i] = t.first;
        l = t.second;
    }
}
 
long long answer() {
    long long ans = max(dp1[D], dp2[D]);
    for (int i = 0; i <= D - 1; i++) {
        ans = max(ans, dp1[i] + dp3[D - i - 1]);
        ans = max(ans, dp2[i] + dp4[D - i - 1]);
    }
    return ans;
}
 
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
    N = n;
    START = start;
    D = d;
    ATTRACTION = attraction;
 
    pre();
    build();
 
    calc1();
    calc2();
    if (START != N - 1)
        calc3();
    if (START)
        calc4();
 
    return answer();
}
 
/*int main() {
    int n, start, d;
    int attraction[100000];
    int i, n_s;
    n_s = scanf("%d %d %d", &n, &start, &d);
    for (i = 0 ; i < n; ++i) {
        n_s = scanf("%d", &attraction[i]);
    }
    cout << findMaxAttraction(n, start, d,  attraction) << endl;
    return 0;
}*/

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 47352 KB Output is correct
2 Correct 47 ms 47352 KB Output is correct
3 Correct 41 ms 47352 KB Output is correct
4 Correct 42 ms 47352 KB Output is correct
5 Correct 49 ms 47352 KB Output is correct
6 Correct 48 ms 47352 KB Output is correct
7 Correct 41 ms 47352 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 274 ms 58220 KB Output is correct
2 Correct 219 ms 58040 KB Output is correct
3 Correct 279 ms 58196 KB Output is correct
4 Correct 345 ms 58104 KB Output is correct
5 Correct 278 ms 56056 KB Output is correct
6 Correct 126 ms 53368 KB Output is correct
7 Correct 178 ms 52600 KB Output is correct
8 Correct 186 ms 53112 KB Output is correct
9 Correct 109 ms 54156 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 47868 KB Output is correct
2 Correct 45 ms 47736 KB Output is correct
3 Correct 46 ms 47952 KB Output is correct
4 Correct 47 ms 47864 KB Output is correct
5 Correct 46 ms 47680 KB Output is correct
6 Correct 43 ms 47480 KB Output is correct
7 Correct 43 ms 47480 KB Output is correct
8 Correct 43 ms 47480 KB Output is correct
9 Correct 37 ms 47556 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 59940 KB Output is correct
2 Correct 368 ms 64684 KB Output is correct
3 Correct 167 ms 52728 KB Output is correct
4 Correct 46 ms 47736 KB Output is correct
5 Correct 43 ms 47480 KB Output is correct
6 Correct 42 ms 47480 KB Output is correct
7 Correct 42 ms 47436 KB Output is correct
8 Correct 431 ms 59740 KB Output is correct
9 Correct 427 ms 59900 KB Output is correct