Submission #1070628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070628		Mardonbekhazratov	Holiday (IOI14_holiday)	C++17	47 / 100	5097 ms	2008 KiB

holiday

#include"holiday.h"
#include<algorithm>
#include<iostream>
#include<vector>

#define ll long long

using namespace std;

struct node{
    int cnt;
    long long sum;
    node(){cnt=0,sum=0;}
};

struct SegTree{

    int N;
    vector<node>tree;

    node merge(node a,node b){
        a.sum+=b.sum;
        a.cnt+=b.cnt;
        return a;
    }

    SegTree(int n){
        N=1;
        while(N<n){N<<=1;}
        
        tree.assign(2*N,node());
    }

    void update(int v,int l,int r,int id,int x){
        if(r-l==1){
            tree[v].sum+=x;
            tree[v].cnt++;
            return;
        }
        
        int mid=(l+r)/2;
        if(id<mid) update(v<<1,l,mid,id,x);
        else update(v<<1|1,mid,r,id,x);
        tree[v]=merge(tree[v<<1],tree[v<<1|1]);
    }

    void update(int id,int x){
        return update(1,0,N,id,x);
    }


    node get(int v,int l,int r,int ql,int qr){
        if(l>=qr || ql>=r) return node();
        if(l>=ql && qr>=r) return tree[v];

        int mid=(l+r)/2;

        return merge(get(v<<1,l,mid,ql,qr),get(v<<1|1,mid,r,ql,qr));
    }

    node get(int l,int r){
        return get(1,0,N,l,r);
    }
};

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    if(d==0) return 0LL;
    ll ans=0;
    vector<int>comp;
    for(int i=0;i<n;i++) comp.push_back(attraction[i]);
    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());
    int m=comp.size();
    for(int l=max(0,start-d+1);l<=start;l++){
        SegTree S(m);
        for(int r=l;r<n;r++){
            S.update(lower_bound(comp.begin(),comp.end(),attraction[r])-comp.begin(),attraction[r]);
            int k=(r-start)+(start-l)+min(r-start,start-l);
            if(k>=d) break;
            int c=d-k;
            if(r>=start){
                int lo=0,hi=m;
                while(hi-lo>1){
                    int mid=(hi+lo)/2;
                    if(S.get(mid,m).cnt>=c) lo=mid;
                    else hi=mid;
                }
                node a=S.get(lo,m);
                // cout<<a.cnt<<'\n';
                a.sum-=1LL*max(0,a.cnt-c)*comp[lo];
                ans=max(ans,a.sum);
            }
        }
    }
    return ans;
}

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