Submission #485421

#	Time	Username	Problem	Language	Result	Execution time	Memory
485421		chienyu_xiong	Holiday (IOI14_holiday)	C++17	100 / 100	1326 ms	30708 KiB

holiday

#include <bits/stdc++.h>

using namespace std;

#pragma region MACROS

#define F first
#define S second

#define pb push_back
#define mp make_pair

#define int long long

#define pii pair<int, int>

#define ee end
#define bb begin
#define all(_) begin(_), end(_)

#define smx(y, x) ((y) = max(x, y))
#define smn(y, x) ((y) = min(x, y))

#pragma endregion

void setIO() {
    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);
    cout.tie(nullptr);
}

const int N = 3e5 + 3;

const int inf = 9e12;
const int mod = 1e9 + 7;

int xyz = 1; // test cases

int n, m, s;

int ans;

int fv[N];
int fp[N];

int gv[N];
int gp[N];

vector<int> ord;
vector<int> idx;
vector<int> arr;

class SEG {
    public:

    int num;
    pii seg[N * 4];

    void init() {
        num = 0;
        for (pii &x : seg)
            x.first = x.second = 0;
    }

    void update(int i, int l, int r, int p, bool v) {
        int mid = (l + r) / 2;
        int il = i << 1 | 0;
        int ir = i << 1 | 1;

        if (l == r) {
            seg[i].S = v;
            seg[i].F = v ? arr[ord[mid]] : 0;
            return;
        }

        if (p <= mid + 0) update(il, l, mid + 0, p, v);
        if (mid + 1 <= p) update(ir, mid + 1, r, p, v);

        seg[i].F = seg[il].F + seg[ir].F;
        seg[i].S = seg[il].S + seg[ir].S;
    }

    int query(int i, int l, int r, int x) {
        if (x >= seg[i].second)
            return seg[i].first;

        int mid = (l + r) / 2;
        int il = i << 1 | 0;
        int ir = i << 1 | 1;

        int res = 0;
        if (l != r && x > 0) {
            int sum = 0;
            res += query(il, l, mid + 0, x - sum); sum += seg[il].second;
            res += query(ir, mid + 1, r, x - sum); sum += seg[ir].second;
        }

        return res;
    }

} seg;

void dac(int l, int r, int xl, int xr) {
    if (l > r) return;

    //cout << l << " " << r << " | " << xl << " " << xr << ": " << seg.seg[1].second << endl;

    int mid = (l + r) / 2;

    int &best = fp[mid] = s;
    int &curr = fv[mid] = 0;
    for (int i = xl; i <= xr; i++) {
        seg.update(1, 0, n - 1, idx[i], true);

        int x = seg.query(1, 0, n - 1, mid - 2 * (i - s));

        if (x >= curr) {
            best = i;
            curr = x;
        }
    }

    if (l != r) {
        // deactivate lights
        for (int i = xl; i <= xr; i++) {
            seg.update(1, 0, n - 1, idx[i], false);
        }

        // IMPORTANT: left first, right second
        dac(l, mid - 0, xl, best);
        dac(mid + 1, r, best, xr);
    }
}

void one(int l, int r, int xl, int xr) {
    if (l > r) return;

    int mid = (l + r) / 2;

    //cout << l << " " << r << " " << mid << " | " << xl << " " << xr << endl;

    int &best = gp[mid] = s - 1;
    int &curr = gv[mid] = 0;
    for (int i = xr; i >= xl; i--) {
        seg.update(1, 0, n - 1, idx[i], true);

        int x = seg.query(1, 0, n - 1, mid - (s - i));

        if (x > curr) {
            best = i;
            curr = x;
        }
    }

    if (l != r) {
        // deactivate lights
        for (int i = xl; i <= xr; i++) {
            seg.update(1, 0, n - 1, idx[i], false);
        }

        // IMPORTANT: right first, left second
        one(l, mid - 0, best, xr);
        one(mid + 1, r, xl, best);
    }

}

bool cmp(int a, int b) {
    return arr[a] > arr[b];
}

void slv() {
    ord.resize(n);
    idx.resize(n);

    iota(all(ord), 0);
    sort(all(ord), cmp);

    for (int i = 0; i < n; i++) {
        idx[ord[i]] = i;
    }

    seg.init(); dac(0, m, s, n - 1);
    seg.init(); one(0, m, 0, s - 1);

    //for (int i = 0; i <= m; i++) cout << i << ": " << fp[i] << " " << fv[i] << endl;
    //for (int i = 0; i <= m; i++) cout << i << ": " << gp[i] << " " << gv[i] << endl;

    for (int i = 0; i <= m; i++) {
        smx(ans, fv[i] + gv[m - i]);
    }
}

int fun() {
    slv();
    reverse(all(arr)); s = n - 1 - s;
    slv();

    return ans;
}

int findMaxAttraction(int32_t _n, int32_t _s, int32_t _m, int32_t attraction[]) {
    n = _n;
    s = _s;
    m = _m;

    arr.resize(n);
    for (int i = 0; i < n; i++) {
        arr[i] = attraction[i];
    }

    return fun();
}

// void run() {
//     cin >> n >> m >> s;

//     arr.resize(n);
//     for (int i = 0; i < n; i++) {
//         cin >> arr[i];
//     }

//     cout << fun() << endl;
// }

// signed main() {
//     setIO();

//     while (xyz--)
//         run();

//     return 0;
// }

Compilation message (stderr)

holiday.cpp:5: warning: ignoring '#pragma region MACROS' [-Wunknown-pragmas]
    5 | #pragma region MACROS
      | 
holiday.cpp:24: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   24 | #pragma endregion
      |

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53