제출 #68942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68942		moonrabbit2	휴가 (IOI14_holiday)	C++17	100 / 100	486 ms	58544 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.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,best=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(query<=0)break;
        if(curr>cans){
            cans=curr;
            best=i;
        }
    }
    ans=max(ans,cans);
    dnc(s,m-1,l,best);
    dnc(m+1,e,best,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;
}

컴파일 시 표준 에러 (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: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53