Submission #1066399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066399		Nika533	Holiday (IOI14_holiday)	C++14	0 / 100	470 ms	13120 KiB

holiday

// #include "holiday.h"
#include <bits/stdc++.h>
using namespace std;

const int NN=1e5+5;

int n,d,st;
long long arr[NN],f[NN*3],ind[NN];

struct segmentTree {
    struct node {
        long long val=0,cnt=0;
    };
    vector<node> t;

    void build(int v, int tl, int tr) {
        t.push_back({0,0});
        if (tl==tr) return;
        int mid=(tl+tr)/2;
        build(v*2,tl,mid); build(v*2+1,mid+1,tr);
    }

    void update(int v, int tl, int tr, int ind, long long a, long long b) {
        if (tl==tr) {
            t[v].val+=a; t[v].cnt+=b; return;
        }
        int mid=(tl+tr)/2;
        if (ind<=mid) update(v*2,tl,mid,ind,a,b);
        else update(v*2+1,mid+1,tr,ind,a,b);
        t[v].val=t[v*2].val+t[v*2+1].val; t[v].cnt=t[v*2].cnt+t[v*2+1].cnt;
    }

    long long query(int v, int tl, int tr, int k) {
        if (k<=0) return 0;
        if (v>=t.size()) return 0;
        if (t[v].cnt<=k) return t[v].val;
        int mid=(tl+tr)/2;
        long long res=query(v*2,tl,mid,k);
        if (t[v*2].cnt<k) res+=query(v*2+1,mid+1,tr,k-t[v*2].cnt);
        return res;
    }
} segtree;

void solve(int tl, int tr, int l, int r, int x) {
    if (tl>tr) return;
    int mid=(tl+tr)/2;

    long long mx_num=0; int mx_ind=0;
    for (int i=l; i<=r; i++) {
        segtree.update(1,st,n-1,ind[i],arr[i],1);
        long long num=segtree.query(1,st,n-1,mid-(i-st)*x);
        if (num>mx_num) {
            mx_num=num; mx_ind=i;
        }
    }
    f[mid]=mx_num;
    for (int i=l; i<=r; i++) segtree.update(1,st,n-1,ind[i],-arr[i],-1);

    for (int i=l; i<mx_ind; i++) segtree.update(1,st,n-1,ind[i],arr[i],1);
    solve(mid+1,tr,mx_ind,r,x);

    for (int i=l; i<mx_ind; i++) segtree.update(1,st,n-1,ind[i],-arr[i],-1);
    solve(tl,mid-1,l,mx_ind,x);
}

long long cal() {
    if (st==0) return 0;

    pair<int,int> arr2[n];
    for (int i=0; i<n; i++) arr2[i]={arr[i],i};
    sort(arr2+st,arr2+n); reverse(arr2+st,arr2+n);
    for (int i=0; i<n; i++) ind[arr2[i].second]=i;
    segtree.t.clear(); segtree.build(1,st,n-1);
    solve(0,d,st,n-1,2);

    long long f1[d+1];
    for (int i=0; i<=d; i++) f1[i]=f[i];
    reverse(arr,arr+n); int in_st=st;
    st=n-1-st; st++;
    for (int i=0; i<n; i++) arr2[i]={arr[i],i};
    sort(arr2+st,arr2+n); reverse(arr2+st,arr2+n);
    for (int i=0; i<n; i++) ind[arr2[i].second]=i;
    segtree.t.clear(); segtree.build(1,st,n-1);
    solve(0,d,st,n-1,1);
    st=in_st; reverse(arr,arr+n);

    long long f2[d+1];
    for (int i=0; i<=d; i++) f2[i]=f[i];

    long long ans=0;
    for (int i=0; i<=d-1; i++) {
        int j=d-i-1;
        ans=max(ans,f1[i]+f2[j]);
    }
    return ans;
}

long long findMaxAttraction(int N, int START, int D, int attraction[]) {
    n=N; st=START; d=D;
    for (int i=0; i<n; i++) arr[i]=attraction[i];

    long long ans1=cal(); reverse(arr,arr+n); st=n-1-st; long long ans2=cal();

    return max(ans1,ans2);
}

Compilation message (stderr)

holiday.cpp: In member function 'long long int segmentTree::query(int, int, int, int)':
holiday.cpp:35:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<segmentTree::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (v>=t.size()) return 0;
      |             ~^~~~~~~~~~

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