Submission #68941

#	Time	Username	Problem	Language	Result	Execution time	Memory
68941		moonrabbit2	Holiday (IOI14_holiday)	C++17	24 / 100	151 ms	57420 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
#define N 100005
using namespace std;
typedef long long ll;
struct node {int l,r,v1;ll v2;};
int n,start,d,a[N],b[N],c,cn,root[N];
map<int,int> mp,to;
ll ans;
node tree[20*N];
void initseg(int nd,int l,int r)
{
    tree[nd].v1=tree[nd].v2=0;
    if(l==r)return;
    tree[nd].l=++cn;
    tree[nd].r=++cn;
    int m=(l+r)/2;
    initseg(tree[nd].l,l,m);
    initseg(tree[nd].r,m+1,r);
}
void add(int ln,int rn,int l,int r,ll v1,ll v2)
{
    tree[rn].v1=tree[ln].v1+1;
    tree[rn].v2=tree[ln].v2+v2;
    if(l==r)return;
    int m=(l+r)/2;
    if(v1<=m){
        tree[rn].r=tree[ln].r;
        tree[rn].l=++cn;
        add(tree[ln].l,tree[rn].l,l,m,v1,v2);
    }
    else{
        tree[rn].l=tree[ln].l;
        tree[rn].r=++cn;
        add(tree[ln].r,tree[rn].r,m+1,r,v1,v2);
    }
}
ll query(int ln,int rn,int l,int r,ll k)
{
    if(k<=0) return 0;
    if(l==r){
        if(k<=tree[rn].v1-tree[ln].v1)
            return (tree[rn].v2-tree[ln].v2)/(tree[rn].v1-tree[ln].v1)*k;
        return tree[rn].v2-tree[ln].v2;
    }
    int m=(l+r)/2;
    ll use=tree[tree[rn].r].v1-tree[tree[ln].r].v1;
    if(use>k)
        return query(tree[ln].r,tree[rn].r,m+1,r,k);
    else
        return tree[tree[rn].r].v2-tree[tree[ln].r].v2+query(tree[ln].l,tree[rn].l,l,m,k-use);
}
void dnc(int s,int e,int l,int r)
{
    if(s>e||l>r)return;
    int m=(s+e)/2,bestl=r,bestr=l;
    ll cans=-1,curr;
    for(int i=l;i<=r;i++){
        curr=query(root[m-1],root[i],1,c,d-i+m-min(start-m,i-start));
        if(curr<=0)break;
        if(curr>cans){
            cans=curr;
            bestl=bestr=i;
        }
        else if(curr==cans){
            bestl=min(bestl,i);
            bestr=max(bestr,i);
        }
    }
    ans=max(ans,cans);
    dnc(s,m-1,l,bestr);
    dnc(m+1,e,bestl,r);
}
ll findMaxAttraction(int n_,int start_,int d_,int attraction[])
{
    n=n_;
    start=start_;
    d=d_;
    for(int i=0;i<n;i++){
        a[i]=attraction[i];
        mp[a[i]]++;
    }
    for(auto &it : mp)
        to[it.first]=++c;
    root[0]=++cn;
    initseg(root[0],1,c);
    for(int i=1;i<=n;i++){
        root[i]=++cn;
        add(root[i-1],root[i],1,c,to[attraction[i-1]],attraction[i-1]);
    }
    start++;
    dnc(1,start,start,n);
    return ans;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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