oj.uz

Submission #591790

# Submission time Handle Problem Language Result Execution time Memory
591790 2022-07-07T22:41:01 Z jeroenodb Holiday (IOI14_holiday) C++14
100 / 100
 398 ms 6000 KB 
#include"holiday.h"
// #include "grader.cpp"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
struct node {
    int active=0;
    ll sm=0;

    void merge(const node& o) {
        active+=o.active;
        sm+=o.sm;
    }
    friend node merge(node a, const node& b) {
        a.merge(b);
        return a;
    }
};
vi cs;
struct segtree {
    int ptwo;
    vector<node> seg;
    segtree(){}
    node& operator[](int i) {
        return seg[i+ptwo];
    }
    segtree(int nn) {
        ptwo=1;
        while(ptwo<nn) ptwo*=2;
        seg.resize(ptwo*2);
    }
    ll good(int d) {
        if(d<0) return -oo;
        int at=1;
        ll ans=0;
        while(at<ptwo) {
            at*=2;
            if(seg[at+1].active<d) {
                ans+=seg[at+1].sm;
                d-=seg[at+1].active;
            } else at++;
        }
        ll tmp = seg[at].sm;
        if(tmp!=0) tmp = min(tmp,cs[at-ptwo]*ll(d));
        return ans+min(seg[at].sm,tmp);
    }
    void update(int i, int val, int sgn) {
        assert(i>=0 and i<ptwo);
        i+=ptwo;
        seg[i].sm+=sgn*val;
        seg[i].active+=sgn;
        for(i/=2;i>=1;i/=2) {
            seg[i] = merge(seg[2*i],seg[2*i+1]);
        }
    }
    void build() {
        for(int i=ptwo-1;i>=1;--i) {
            seg[i] = merge(seg[2*i],seg[2*i+1]);
        }
    }
};
segtree seg;


ll ans=0;
void solve(int l, int r, int a, int b, int d, int atr[]) {
    if(a>b or l>r) return;
    int mid = (l+r)/2;
    pair<ll,int> opt;
    if(d>=r-mid+1) {
        d++;
        for(int i=mid;i<=r;++i) {
            d--;
            seg.update(atr[i],cs[atr[i]],1);
        }
        opt = {seg.good(d),a};

        for(int i=a+1;i<=b;++i) {
            seg.update(atr[i],cs[atr[i]],1);
            d-=2;
            opt = max(opt,{seg.good(d),i});
        }
        ans = max(ans,opt.first);
        for(int i=a+1;i<=b;++i) {
            seg.update(atr[i],cs[atr[i]],-1);
            d+=2;
        }

        solve(l,mid-1,a,opt.second,d-1,atr);
        for(int i=mid;i<=r;++i) {
            d++;
            seg.update(atr[i],cs[atr[i]],-1);
        }
        d--;
    }
    for(int i=a+1;i<=opt.second;++i) {
        seg.update(atr[i],cs[atr[i]],1);
        d-=2;
    }
    solve(mid+1,r,opt.second,b,d,atr);
    for(int i=a+1;i<=opt.second;++i) {
        seg.update(atr[i],cs[atr[i]],-1);
    }
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    ans=0;
    cs = vi(attraction,attraction+n);
    sort(all(cs));
    cs.erase(unique(all(cs)),cs.end());
    for(int i=0;i<n;++i) {
        attraction[i] = lower_bound(all(cs),attraction[i])-cs.begin();
    }
    seg = segtree(cs.size());
    for(int rep=0;rep<2;++rep) {
        solve(0,start,start,n-1,d,attraction);
        reverse(attraction,attraction+n);
        start=n-1-start;
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1068 KB Output is correct
2 Correct 17 ms 1088 KB Output is correct
3 Correct 20 ms 980 KB Output is correct
4 Correct 22 ms 1088 KB Output is correct
5 Correct 48 ms 944 KB Output is correct
6 Correct 15 ms 792 KB Output is correct
7 Correct 27 ms 892 KB Output is correct
8 Correct 32 ms 940 KB Output is correct
9 Correct 11 ms 768 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 6 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 ms 596 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1064 KB Output is correct
2 Correct 106 ms 5180 KB Output is correct
3 Correct 163 ms 2916 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 2 ms 684 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 373 ms 6000 KB Output is correct
9 Correct 398 ms 6000 KB Output is correct