Submission #1241790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241790		BlockOG	휴가 (IOI14_holiday)	C++20	0 / 100	337 ms	12248 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>

// mrrrrow meeeow :3
// go play vivid/stasis! it's free on steam

#define f first
#define s second
using namespace std;

const int N = 1 << 17;
pair<int, long long> st[N * 2];

int to_sorted[100000];
pair<int, int> sorted[100000];

long long resl[250001], resll[250001];
long long resr[250001], resrl[250001];

long long get(int x) {
    long long res = 0;
    for (int i = 1; x > 0 && i < N;) {
        if (st[i*2+1].f > x) {
            i = i*2+1;
        } else {
            i = i*2;
            x -= st[i+1].f;
            res += st[i+1].s;
            
            if (st[i].f <= x) {
                res += st[i].s;
                break;
            }
        }
    }
    
    return res;
}

int off = 0;

void activate(int i) {
    i = N + to_sorted[off + i];
    st[i] = {1, sorted[i - N].f};
    for (i /= 2; i > 0; i /= 2) st[i] = {st[i*2].f + st[i*2+1].f, st[i*2].s + st[i*2+1].s};
}

void deactivate(int i) {
    i = N + to_sorted[off + i];
    st[i] = {0, 0};
    for (i /= 2; i > 0; i /= 2) st[i] = {st[i*2].f + st[i*2+1].f, st[i*2].s + st[i*2+1].s};
}

long long recurse(int dl, int dr, int rl, int rr, long long res[], int mul=1) {
    int d = (dl + dr) / 2;
    
    int r = rl;
    long long m = get(d - r*mul);
    
    for (int i = rl; i <= rr; i++) {
        activate(i);
        
        long long nm = get(d - i*mul);
        if (nm > m) r = i, m = nm;
    }
    
    res[d] = m;
    
    for (int i = rl; i <= rr; i++) deactivate(i);
    if (dl <= d - 1) res[d] = max(res[d], recurse(dl, d - 1, rl, r, res, mul));
    activate(r);
    if (d + 1 <= dr) recurse(d + 1, dr, r, rr, res, mul);
    
    return res[d];
}

long long findMaxAttraction(int n, int s, int d, int attraction[]) {
    reverse(attraction, attraction + s);
    for (int i = 0; i < n; i++) sorted[i] = {attraction[i], i};
    sort(sorted, sorted + n);
    for (int i = 0; i < n; i++) to_sorted[sorted[i].s] = i;
    
    recurse(0, d-1, 0, s - 1, resl+1);
    for (int i = 1; i < 2*N; i++) st[i] = {0, 0};
    recurse(0, d-1, 0, s - 1, resll+1, 2);
    for (int i = 1; i < 2*N; i++) st[i] = {0, 0}; off = s;
    recurse(0, d, 0, n - s - 1, resr);
    for (int i = 1; i < 2*N; i++) st[i] = {0, 0};
    recurse(0, d, 0, n - s - 1, resrl, 2);
    
    long long res = 0;
    for (int i = 0; i <= d; i++) res = max(res, max(resl[i] + resrl[d - i], resll[i] + resr[d - i]));
    return res;
}

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