제출 #1304303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304303		activedeltorre	휴가 (IOI14_holiday)	C++20	24 / 100	1376 ms	36900 KiB

holiday

#include"holiday.h"

#include <vector>
#include <algorithm>
using namespace std;
int poz[100005];
int nodes=0;
//int root[10005];
//int fiust[3200005];
//int fiudr[3200005];
long long rez[300005][4];
int unmap[100005];
vector<pair<int,int> >v0,v1,v2,v3;
vector<pair<int,int> >event[30005];
int stanga[300005];
int idx[300005];
int stpos[300005];
int strr[3005][3005];
int noduri=0;
int overtook[300005];
int nmax,n,dmax;
int find(int a)
{
    if(overtook[a]==a)
    {
        return a;
    }
    return overtook[a]=find(overtook[a]);
}
long long heighest(int index,int k)
{
    long long suma=0;
    for(int i=nmax;i>=0;i--)
    {
        if(strr[index][i]>=1 && k>=1)
        {
            suma=suma+unmap[i];
            k--;
        }
    }
    return suma;
}
long long value(int index,int timp)
{
    if(timp<=stpos[index])
    {
        return 0;
    }
    return heighest(index,timp-stpos[index]);
}
void compare(int idx1,int idx2)
{
    int st=0,dr=dmax;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(value(idx1,mij)<value(idx2,mij))
        {
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    if(dr+1<=dmax)
    {
        event[dr+1].push_back({1,idx2});
    }
}
void add(int index,int startpos)
{
    if(noduri==0)
    {
        noduri++;
        stpos[noduri]=startpos;
        stanga[noduri]=-1;
        overtook[noduri]=noduri;
        for(int i=0;i<=nmax;i++)
        {
            strr[noduri][i]=0;
        }
        strr[noduri][poz[index]]=1;
    }
    else
    {
        noduri++;
        stpos[noduri]=startpos;
        stanga[noduri]=noduri-1;
        overtook[noduri]=noduri;
        for(int i=0;i<=nmax;i++)
        {
            strr[noduri][i]=strr[noduri-1][i];
        }
        strr[noduri][poz[index]]=1;
        compare(stanga[noduri],noduri);
    }
}
void overtake(int index)
{
    if(overtook[index]==index)
    {
        overtook[stanga[index]]=index;
        stanga[index]=stanga[stanga[index]];
        if(stanga[index]!=-1)
        {
            compare(stanga[index],index);
        }
    }
}
void calc(int tiprez,vector<pair<int,int> >vec)
{
    noduri=0;
    for(int i=0;i<vec.size();i++)
    {
        event[vec[i].first].push_back({0,vec[i].second});
    }
    for(int i=0;i<=dmax;i++)
    {
        while(event[i].size())
        {
            auto x=event[i].back();
            event[i].pop_back();
            if(x.first==0)
            {
                add(x.second,i);
            }
            else
            {
                overtake(x.second);
            }
        }
        if(noduri>=1)
        rez[i][tiprez]=value(find(1),i);
    }
}
long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
    nmax=n;
    dmax=d;
    start++;
    vector<pair<int,int> >vec;
    for(int i=1; i<=n; i++)
    {
        vec.push_back({attraction[i-1],i});
    }
    sort(vec.begin(),vec.end());
    for(int i=0;i<n;i++)
    {
        poz[vec[i].second]=i;
        unmap[i]=vec[i].first;
    }
    for(int i=start;i<=n;i++)
    {
        v0.push_back({i-start,i});
        v1.push_back({(i-start)*2,i});
    }
    for(int i=start-1;i>=1;i--)
    {
        v2.push_back({start-i,i});
        v3.push_back({(start-i)*2,i});
    }
    calc(0,v0);
    calc(1,v1);
    calc(2,v2);
    calc(3,v3);
    long long sol=0;
    for(int i=0;i<=dmax;i++)
    {
        sol=max(sol,rez[i][0]+rez[d-i][3]);
        sol=max(sol,rez[i][1]+rez[d-i][2]);
    }
    return sol;
}

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