oj.uz

답안 #579089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
579089 2022-06-18T11:21:08 Z tranxuanbach 휴가 (IOI14_holiday) C++17
100 / 100
 705 ms 17212 KB 
#ifndef FEXT

#include "holiday.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

struct segment_tree{
    pair <int, ll> seg[1 << 18];

    void build(int id, int l, int r){
        if (l == r){
            seg[id] = make_pair(0, 0);
            return;
        }
        int mid = (l + r) >> 1;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        seg[id] = make_pair(0, 0);
    }

    void update(int id, int l, int r, int i, int val){
        if (l == r){
            seg[id].fi++;
            seg[id].se += val;
            return;
        }
        int mid = (l + r) >> 1;
        if (i <= mid){
            update(id * 2, l, mid, i, val);
        }
        else{
            update(id * 2 + 1, mid + 1, r, i, val);
        }
        seg[id] = make_pair(seg[id * 2].fi + seg[id * 2 + 1].fi, seg[id * 2].se + seg[id * 2 + 1].se);
    }

    ll sum_max(int id, int l, int r, int x){
        if (x >= seg[id].fi){
            return seg[id].se;
        }
        if (l == r or x <= 0){
            return 0;
        }
        int mid = (l + r) >> 1;
        if (seg[id * 2 + 1].fi > x){
            return sum_max(id * 2 + 1, mid + 1, r, x);
        }
        else{
            return sum_max(id * 2, l, mid, x - seg[id * 2 + 1].fi) + seg[id * 2 + 1].se;
        }
    }
} seg;

const int N = 1e5 + 5, M = 3e5 + 5;

#define left __left__
#define right __right__
int left[N], right[N];

pair <int, ll> ansleft[M], ansright[M];

int pos[N];

int idxopt;

void dnc(int n, int a[], pair <int, ll> ans[], int l, int r, int optl, int optr, queue <tuple <int, int, int, int>> &qu){
    int mid = (l + r) >> 1;
    ans[mid] = make_pair(-1, 0);

    if (optl < idxopt){
        seg.build(1, 0, n - 1);
        idxopt = 0;
        seg.update(1, 0, n - 1, pos[idxopt], a[idxopt]);
    }
    ForE(opt, optl, optr){
        while (idxopt < opt){
            idxopt++;
            seg.update(1, 0, n - 1, pos[idxopt], a[idxopt]);
        }
        ll val = seg.sum_max(1, 0, n - 1, mid - opt);
        if (ans[mid].fi == -1 or ans[mid].se < val){
            ans[mid] = make_pair(opt, val);
        }
    }

    // if (mid < 10){
    //     cout << "dnc " << l << ' ' << r << ' ' << mid << ' ' << ans[mid].fi << ' ' << ans[mid].se << endl;
    // }

    if (l < mid){
        qu.emplace(l, mid - 1, optl, ans[mid].fi);
    }
    if (mid < r){
        qu.emplace(mid + 1, r, ans[mid].fi, optr);
    }
}

void findMaxAttractionStart1(int n, int a[], pair <int, ll> ans[]){
    // cout << "findMaxAttractionStart1 " << n << endl;
    // For(i, 0, n){
    //     cout << a[i] << ' ';
    // } cout << endl;
    {
        vpii b;
        For(i, 0, n){
            b.emplace_back(a[i], i);
        }
        sort(bend(b));
        For(i, 0, n){
            pos[b[i].se] = i;
        }
    }

    idxopt = n;

    queue <tuple <int, int, int, int>> qu;
    qu.emplace(0, 2 * n, 0, n - 1);

    while (!qu.empty()){
        int l, r, optl, optr; tie(l, r, optl, optr) = qu.front(); qu.pop();
        dnc(n, a, ans, l, r, optl, optr, qu);
    }

    For(i, 2 * n + 1, M){
        ans[i] = ans[i - 1];
    }

    // For(i, 0, 10){
    //     cout << i << ' ' << ans[i].fi << ' ' << ans[i].se << endl;
    // }
}

ll findMaxAttraction(int n, int start, int d, int a[]){
    ll ans = 0;

    FordE(i, start, 0){
        left[start - i] = a[i];
    }
    findMaxAttractionStart1(start + 1, left, ansleft);
    ForE(dl, 0, d){
        ans = max(ans, ansleft[dl].se);
    }
    if (start < n - 1){
        For(i, start + 1, n){
            right[i - start - 1] = a[i];
        }
        findMaxAttractionStart1(n - start - 1, right, ansright);
        ForE(dl, 0, d){
            int dr = d - dl - ansleft[dl].fi - 1;
            if (!(0 <= dr and dr <= d)){
                continue;
            }
            // cout << "dl dr left " << dl << ' ' << dr << endl;
            // cout << ansleft[dl].fi << ' ' << ansleft[dl].se << ' ' << ansright[dr].fi << ' ' << ansright[dr].se << endl;
            ans = max(ans, ansleft[dl].se + ansright[dr].se);
        }
    }

    For(i, start, n){
        right[i - start] = a[i];
    }
    findMaxAttractionStart1(n - start, right, ansright);
    ForE(dr, 0, d){
        ans = max(ans, ansright[dr].se);
    }
    if (start > 0){
        FordE(i, start - 1, 0){
            left[start - 1 - i] = a[i];
        }
        findMaxAttractionStart1(start, left, ansleft);
        ForE(dr, 0, d){
            int dl = d - dr - ansright[dr].fi - 1;
            if (!(0 <= dl and dl <= d)){
                continue;
            }
            // cout << "dl dr right " << dl << ' ' << dr << endl;
            // cout << ansleft[dl].fi << ' ' << ansleft[dl].se << ' ' << ansright[dr].fi << ' ' << ansright[dr].se << endl;
            ans = max(ans, ansleft[dl].se + ansright[dr].se);
        }
    }
    return ans;
}

#ifdef FEXT

int a[100005];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    int n, start, d; cin >> n >> start >> d;
    For(i, 0, n){
        cin >> a[i];
    }

    ll ans = findMaxAttraction(n, start, d, a);
    cout << ans << endl;
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10068 KB Output is correct
2 Correct 8 ms 10044 KB Output is correct
3 Correct 7 ms 10068 KB Output is correct
4 Correct 7 ms 10044 KB Output is correct
5 Correct 9 ms 10068 KB Output is correct
6 Correct 9 ms 10004 KB Output is correct
7 Correct 8 ms 10068 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 433 ms 17020 KB Output is correct
2 Correct 296 ms 17056 KB Output is correct
3 Correct 408 ms 17056 KB Output is correct
4 Correct 301 ms 17140 KB Output is correct
5 Correct 640 ms 16872 KB Output is correct
6 Correct 169 ms 12040 KB Output is correct
7 Correct 327 ms 13636 KB Output is correct
8 Correct 404 ms 13832 KB Output is correct
9 Correct 120 ms 11772 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 10376 KB Output is correct
2 Correct 14 ms 10376 KB Output is correct
3 Correct 14 ms 10324 KB Output is correct
4 Correct 19 ms 10324 KB Output is correct
5 Correct 17 ms 10196 KB Output is correct
6 Correct 10 ms 10068 KB Output is correct
7 Correct 10 ms 10068 KB Output is correct
8 Correct 10 ms 10044 KB Output is correct
9 Correct 10 ms 10164 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 448 ms 16888 KB Output is correct
2 Correct 529 ms 17212 KB Output is correct
3 Correct 273 ms 12156 KB Output is correct
4 Correct 18 ms 10248 KB Output is correct
5 Correct 10 ms 10172 KB Output is correct
6 Correct 10 ms 10068 KB Output is correct
7 Correct 10 ms 10044 KB Output is correct
8 Correct 676 ms 14112 KB Output is correct
9 Correct 705 ms 14164 KB Output is correct