oj.uz

Submission #329483

# Submission time Handle Problem Language Result Execution time Memory
329483 2020-11-21T10:09:13 Z tnk2908 Holiday (IOI14_holiday) C++14
100 / 100
 973 ms 8172 KB 
//
//  main.cpp
//  holiday
//
//  Created by Trần Nam Khánh on 11/21/20.
//

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int nax=1e5+1;
const int inf=1e9;
struct node
{
    long long s;
    int ac;
}seg[4*nax];
void build(int id,int l,int r)
{
    seg[id].s=0;
    seg[id].ac=0;
    if(l==r)
    {

        return;
    }
    int mid=(l+r)>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int k,int val,int stat)
{
    if(k<l||r<k)return;
    if(l==r)
    {
        seg[id].ac=stat;
        seg[id].s=val;
        return;
    }
    int mid=(l+r)>>1;
    update(id*2,l,mid,k,val,stat);
    update(id*2+1,mid+1,r,k,val,stat);
    seg[id].ac=seg[id*2].ac+seg[id*2+1].ac;
    seg[id].s=seg[id*2].s+seg[id*2+1].s;
}
long long query(int id,int l,int r,int x)
{
    long long res=0;
    if(x<=0)return 0;
    if(seg[id].ac<=x)
    {
        return seg[id].s;
    }
    int mid=(l+r)>>1;
    res=query(id*2,l,mid,min(x,seg[id*2].ac))+query(id*2+1,mid+1,r,x-seg[id*2].ac);
    return res;
}
int n,st,d,a[nax],pl[nax],attraction[nax];
long long dp[nax];
int ab(int a)
{
    if(a<0)return -a;else return a;
}
void dc1(int lo,int hi,int lovl,int hivl)
{
    if(lo>hi)return;
    int mid=(lo+hi)>>1,x=lovl;
    for(int i=mid;i<=hi;i++)
    {
        update(1,1,n,pl[i],a[i],1);
    }
    for(int i=lovl;i<=hivl;i++)
    {
        int tmpd=d-min(ab(st-mid),ab(i-st))-ab(mid-i);
        if(tmpd<0)break;
        update(1,1,n,pl[i],a[i],1);
        long long tmp=query(1,1,n,tmpd);
        if(dp[mid]<tmp)
        {
            dp[mid]=tmp;
            x=i;
        }
    }
    for(int i=mid;i<=hi;i++)
    {
        update(1,1,n,pl[i],0,0);
    }
    for(int i=x;i<=hivl;i++)update(1,1,n,pl[i],0,0);
    dc1(mid+1,hi,x,hivl);
    for(int i=mid;i<=hi;i++)
    {
        update(1,1,n,pl[i],a[i],1);
    }
    for(int i=lovl;i<=x;i++)update(1,1,n,pl[i],0,0);
    dc1(lo,mid-1,lovl,x);
}
long long findMaxAttraction(int N, int start, int days, int attraction[])
{
    long long ans=0;
    pair<int,int>b[nax];
    n=N;st=start;d=days;
    st++;
    for(int i=1;i<=n;i++)
    {
        a[i]=attraction[i-1];
        b[i].first=-a[i];
        b[i].second=i;
        dp[i]=-inf;
    }
    build(1,1,n);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
    {
        pl[b[i].second]=i;
    }
    dc1(1,st,st,n);
    for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 1 ms 1132 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct
7 Correct 1 ms 1132 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 7404 KB Output is correct
2 Correct 71 ms 7404 KB Output is correct
3 Correct 65 ms 7532 KB Output is correct
4 Correct 74 ms 7320 KB Output is correct
5 Correct 85 ms 7276 KB Output is correct
6 Correct 22 ms 2796 KB Output is correct
7 Correct 42 ms 4280 KB Output is correct
8 Correct 53 ms 4588 KB Output is correct
9 Correct 16 ms 2540 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1388 KB Output is correct
2 Correct 11 ms 1388 KB Output is correct
3 Correct 11 ms 1388 KB Output is correct
4 Correct 12 ms 1408 KB Output is correct
5 Correct 11 ms 1400 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 4 ms 1132 KB Output is correct
8 Correct 4 ms 1132 KB Output is correct
9 Correct 4 ms 1132 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 8172 KB Output is correct
2 Correct 67 ms 8044 KB Output is correct
3 Correct 316 ms 4588 KB Output is correct
4 Correct 12 ms 1260 KB Output is correct
5 Correct 4 ms 1132 KB Output is correct
6 Correct 4 ms 1132 KB Output is correct
7 Correct 4 ms 1132 KB Output is correct
8 Correct 961 ms 8172 KB Output is correct
9 Correct 973 ms 8172 KB Output is correct