oj.uz

답안 #245992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245992 2020-07-08T00:00:04 Z gs18115 휴가 (IOI14_holiday) C++14
100 / 100
 267 ms 54264 KB 
#include"holiday.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
struct node
{
    int cnt;
    ll sum;
    int l,r;
    node(){sum=0;cnt=l=r=0;}
}tree[2222222];
int tct;
void upd(int&n,int s,int e,int x,int p)
{
    tree[++tct]=tree[n];
    n=tct;
    tree[n].cnt++;
    tree[n].sum+=p;
    if(s==e)
        return;
    int m=s+(e-s)/2;
    if(x>m)
        upd(tree[n].r,m+1,e,x,p);
    else
        upd(tree[n].l,s,m,x,p);
    return;
}
ll query(int l,int r,int k)
{
    if(k<=0)
        return 0;
    if(k>=tree[r].cnt-tree[l].cnt)
        return tree[r].sum-tree[l].sum;
    if(tree[r].l==0&&tree[r].r==0)
        return k*(tree[r].sum/tree[r].cnt);
    node&ln=tree[tree[l].r];
    node&rn=tree[tree[r].r];
    if(k>=rn.cnt-ln.cnt)
        return(rn.sum-ln.sum)+query(tree[l].l,tree[r].l,k-(rn.cnt-ln.cnt));
    return query(tree[l].r,tree[r].r,k);
}
int rt[100010];
int n,st,d;
ll ans;
void dnc1(int s,int e,int as,int ae)
{
    if(s>e)
        return;
    int m=s+(e-s)/2;
    int mxi=-1;
    ll cans=-1;
    for(int i=as;i<=ae;i++)
    {
        ll cur=query(rt[i-1],rt[m],d-(st+m-i*2));
        if(cur>cans)
            cans=cur,mxi=i;
    }
    ans=max(ans,cans);
    dnc1(s,m-1,as,mxi);
    dnc1(m+1,e,mxi,ae);
    return;
}
void dnc2(int s,int e,int as,int ae)
{
    if(s>e)
        return;
    int m=s+(e-s)/2;
    int mxi=-1;
    ll cans=-1;
    for(int i=as;i<=ae;i++)
    {
        ll cur=query(rt[m-1],rt[i],d-(i*2-st-m));
        if(cur>cans)
            cans=cur,mxi=i;
    }
    ans=max(ans,cans);
    dnc2(s,m-1,as,mxi);
    dnc2(m+1,e,mxi,ae);
    return;
}
long long int findMaxAttraction(int n,int start,int d,int attraction[])
{
    ::n=n;
    ::st=start+1;
    ::d=d;
    vector<int>v(n);
    for(int i=0;i<n;i++)
        v[i]=attraction[i];
    vector<int>cv=v;
    sort(all(cv));
    cv.erase(unique(all(cv)),cv.end());
    int m=cv.size();
    v.insert(v.begin(),0);
    for(int i=0;i++<n;)
        upd(rt[i]=rt[i-1],1,m,upper_bound(all(cv),v[i])-cv.begin(),v[i]);
    dnc1(st,min(n,st+d-1),1,st);
    dnc2(max(1,st-d+1),st,st,n);
    return ans;
    return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 52480 KB Output is correct
2 Correct 32 ms 52480 KB Output is correct
3 Correct 32 ms 52480 KB Output is correct
4 Correct 32 ms 52472 KB Output is correct
5 Correct 31 ms 52480 KB Output is correct
6 Correct 31 ms 52480 KB Output is correct
7 Correct 32 ms 52480 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 54016 KB Output is correct
2 Correct 46 ms 54264 KB Output is correct
3 Correct 49 ms 54264 KB Output is correct
4 Correct 47 ms 54264 KB Output is correct
5 Correct 64 ms 54264 KB Output is correct
6 Correct 42 ms 53248 KB Output is correct
7 Correct 50 ms 53496 KB Output is correct
8 Correct 53 ms 53760 KB Output is correct
9 Correct 37 ms 52984 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 52600 KB Output is correct
2 Correct 32 ms 52608 KB Output is correct
3 Correct 33 ms 52608 KB Output is correct
4 Correct 35 ms 52608 KB Output is correct
5 Correct 34 ms 52600 KB Output is correct
6 Correct 32 ms 52608 KB Output is correct
7 Correct 33 ms 52480 KB Output is correct
8 Correct 32 ms 52480 KB Output is correct
9 Correct 32 ms 52480 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 54008 KB Output is correct
2 Correct 82 ms 54008 KB Output is correct
3 Correct 82 ms 53240 KB Output is correct
4 Correct 35 ms 52608 KB Output is correct
5 Correct 34 ms 52472 KB Output is correct
6 Correct 32 ms 52480 KB Output is correct
7 Correct 32 ms 52608 KB Output is correct
8 Correct 259 ms 54008 KB Output is correct
9 Correct 267 ms 54008 KB Output is correct