제출 #1304311

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

holiday

#include"holiday.h"

#include <vector>
#include <algorithm>
using namespace std;
int poz[100005];
long long rez[300005][4];
int unmap[100005];
vector<pair<int,int> >v0,v1,v2,v3;
vector<pair<int,int> >event[300005];
int stanga[100005];
int idx[100005];
int stpos[100005];
int noduri=0;
int overtook[100005];
int nmax,n,dmax;
long long nodes=0;
struct nodus
{
    int fiu1,fiu2,cnt;
    long long suma;
};
nodus nod[2000000];
long long v[200005];
int root[100005];
void build(long long node,long long st,long long dr)
{
    if(st==dr)
    {
        nod[node].suma=0;
        nod[node].cnt=0;
        return;
    }
    long long mij=(st+dr)/2;
    nod[node].fiu1=node*2;
    nod[node].fiu2=node*2+1;
    nodes=max(nodes,node*2+1);
    build(nod[node].fiu1,st,mij);
    build(nod[node].fiu2,mij+1,dr);
    nod[node].suma=nod[nod[node].fiu1].suma+nod[nod[node].fiu2].suma;
    nod[node].cnt=nod[nod[node].fiu1].cnt+nod[nod[node].fiu2].cnt;
}
void update(long long node,long long st,long long dr,long long poz,long long val)
{
    if(st==dr)
    {
        nodes++;
        nod[nodes].suma=val;
        nod[nodes].cnt=1;
        return;
    }
    long long mij=(st+dr)/2;
    if(poz<=mij)
    {
        update(nod[node].fiu1,st,mij,poz,val);
        nodes++;
        nod[nodes].fiu1=nodes-1;
        nod[nodes].fiu2=nod[node].fiu2;
    }
    else
    {
        update(nod[node].fiu2,mij+1,dr,poz,val);
        nodes++;
        nod[nodes].fiu2=nodes-1;
        nod[nodes].fiu1=nod[node].fiu1;
    }
    nod[nodes].suma=nod[nod[nodes].fiu1].suma+nod[nod[nodes].fiu2].suma;
    nod[nodes].cnt=nod[nod[nodes].fiu1].cnt+nod[nod[nodes].fiu2].cnt;
}
long long querry(long long node,long long st,long long dr,long long k)
{
    long long mij=(st+dr)/2;
    if(st==dr && k>=1)
    {
        return nod[node].suma;
    }
    else if(st==dr)
    {
        return 0;
    }
    if(nod[nod[node].fiu2].cnt<=k)
    {
        return nod[nod[node].fiu2].suma+querry(nod[node].fiu1,st,mij,k-nod[nod[node].fiu2].cnt);
    }
    return querry(nod[node].fiu2,mij+1,dr,k);
}
int find(int a)
{
    if(overtook[a]==a)
    {
        return a;
    }
    return overtook[a]=find(overtook[a]);
}
long long heighest(int index,int k)
{
    return querry(root[index],0,nmax,k);
}
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=1;i<=nodes;i++)
        {
            nod[i].cnt=0;
            nod[i].fiu1=0;
            nod[i].fiu2=0;
            nod[i].suma=0;
        }
        nodes=0;
        nodes++;
        root[noduri]=1;
        build(1,0,nmax);
        update(root[noduri],0,nmax,poz[index],unmap[poz[index]]);
        root[noduri]=nodes;
    }
    else
    {
        noduri++;
        stpos[noduri]=startpos;
        stanga[noduri]=noduri-1;
        overtook[noduri]=noduri;
        nodes++;
        root[noduri]=nodes;
        nod[root[noduri]].fiu1=nod[root[noduri-1]].fiu1;
        nod[root[noduri]].fiu2=nod[root[noduri-1]].fiu2;
        nod[root[noduri]].suma=nod[root[noduri-1]].suma;
        nod[root[noduri]].cnt=nod[root[noduri-1]].cnt;
        update(root[noduri],0,nmax,poz[index],unmap[poz[index]]);
        root[noduri]=nodes;
        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=min(d,3*n);
    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