제출 #747099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
747099		nicksms	휴가 (IOI14_holiday)	C++17	100 / 100	226 ms	49300 KiB

holiday

#include"holiday.h"

/**
 *      Author:  Nicholas Winschel
 *      Created: 05.23.2023 11:04:21
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

// NOT ORIGINAL
// credit https://oj.uz/submission/211797 for solution ideas
// my idea was so much more shenanigans lol
// basically for maintianing sum of k smallest i didnt see the persistent segtree
// so i had a two poitners idea that would do some funny pushleft/pushright to do the dnc dp

struct pst {
    struct node {ll v=0; int c=0,l=0,r=0;};
    int N, nind=0,rind=0;
    V<node> nodes;
    vi root,vals;
    pst (vi &&_): N(_.size()), nodes(2000000), root(N+1), vals(move(_)) {}
    void add(int x, int s, int e, int &i) {
        int p = i; i = ++nind;
        nodes[i] = {nodes[p].v + vals[x], nodes[p].c+1, nodes[p].l, nodes[p].r};
        if (s==e) return;
        int m = (s+e)>>1;
        if (x <= m) add(x, s, m, nodes[i].l);
        else add(x, m+1, e, nodes[i].r);
    }
    void add(int x) {rind++; add(x, 0, N-1, root[rind]=root[rind-1]);}
    ll sum (int k, int s, int e, int i, int j) {
        if (nodes[j].c - nodes[i].c <= k) return nodes[j].v-nodes[i].v;
        if (s==e) return vals[s]*ll(k); // this is cause pos dup
        int m = (s+e)>>1,
            cr = nodes[nodes[j].r].c-nodes[nodes[i].r].c;
        if (k <= cr) return sum(k,m+1,e,nodes[i].r,nodes[j].r);
        else return sum(k-cr,s,m,nodes[i].l,nodes[j].l)+(nodes[nodes[j].r].v - nodes[nodes[i].r].v);
    }
    ll sum (int k, int l, int r) {
        return sum(k, 0, N-1, root[l],root[r+1]);
    }
};

long long int findMaxAttraction(int n, int start, int d, int a[]) {
    vi x(a,a+n);
    sort(x.begin(),x.end());
    for (int i = 0; i < n; i++) a[i]=lower_bound(x.begin(),x.end(),a[i])-x.begin();
    ll b = 0;
    pst sg(move(x));
    for (int i = 0; i < n; i++) sg.add(a[i]);
    auto dnq = [&](int s, int e, int optl, int optr, auto &&dnq) -> void {
        if (s > e || optl > optr) return;
        int m = (s+e)>>1;
        pair<ll,int> cb = {-1,-1};
        for (int t = optl; t <= optr; t++) {
            cb=max(cb, {sg.sum(d- (t-m + min(t-start,start-m)),m,t),t});
        }
        b=max(b,cb.f);
        dnq(s,m-1,optl,cb.s,dnq);
        dnq(m+1,e,cb.s,optr,dnq);
    };
    dnq(max(start-d,0),start,start,min(start+d,n-1),dnq);
    return b;
}

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