oj.uz

Submission #747099

# Submission time Handle Problem Language Result Execution time Memory
747099 2023-05-23T15:49:30 Z nicksms Holiday (IOI14_holiday) C++17
100 / 100
 226 ms 49300 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47564 KB Output is correct
2 Correct 22 ms 47572 KB Output is correct
3 Correct 25 ms 47588 KB Output is correct
4 Correct 22 ms 47652 KB Output is correct
5 Correct 22 ms 47596 KB Output is correct
6 Correct 22 ms 47572 KB Output is correct
7 Correct 22 ms 47608 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 48624 KB Output is correct
2 Correct 61 ms 48504 KB Output is correct
3 Correct 49 ms 48612 KB Output is correct
4 Correct 47 ms 48644 KB Output is correct
5 Correct 56 ms 48708 KB Output is correct
6 Correct 33 ms 47924 KB Output is correct
7 Correct 49 ms 48168 KB Output is correct
8 Correct 61 ms 48204 KB Output is correct
9 Correct 28 ms 47812 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47596 KB Output is correct
2 Correct 24 ms 47680 KB Output is correct
3 Correct 23 ms 47672 KB Output is correct
4 Correct 26 ms 47628 KB Output is correct
5 Correct 24 ms 47608 KB Output is correct
6 Correct 22 ms 47640 KB Output is correct
7 Correct 23 ms 47632 KB Output is correct
8 Correct 22 ms 47624 KB Output is correct
9 Correct 23 ms 47552 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 49216 KB Output is correct
2 Correct 59 ms 49300 KB Output is correct
3 Correct 70 ms 48332 KB Output is correct
4 Correct 24 ms 47560 KB Output is correct
5 Correct 21 ms 47616 KB Output is correct
6 Correct 22 ms 47676 KB Output is correct
7 Correct 24 ms 47668 KB Output is correct
8 Correct 226 ms 49264 KB Output is correct
9 Correct 218 ms 49296 KB Output is correct