제출 #1285017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285017		tudor_costin	치료 계획 (JOI20_treatment)	C++20	100 / 100	1388 ms	333256 KiB

treatment

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Mmax=1e5+5;
struct tratament
{
    int t,l,r,c;
};
tratament trat[Mmax];
bool viz[Mmax];
map<int,int> nrm;
vector<pair<int,int>> g[Mmax];
set<pair<int,int>> aint[4*Mmax][5];
vector<int> intime[Mmax];
void build(int nod,int l,int r)
{
    if(l==r)
    {
        for(int idx:intime[l])
        {
            aint[nod][1].insert({trat[idx].l+trat[idx].t-1,idx});
            aint[nod][2].insert({trat[idx].l-trat[idx].t-1,idx});
        }
        return;
    }
    int mid=(l+r)/2;
    build(2*nod,l,mid);
    build(2*nod+1,mid+1,r);
    for(auto x:aint[2*nod][1]) aint[nod][1].insert(x);
    for(auto x:aint[2*nod][2]) aint[nod][2].insert(x);
    for(auto x:aint[2*nod+1][1]) aint[nod][1].insert(x);
    for(auto x:aint[2*nod+1][2]) aint[nod][2].insert(x);
    return;
}
vector<int> query(int nod,int l,int r,int st,int dr,int cmp,int tip)
{
    if(st<=l && r<=dr)
    {
        vector<pair<int,int>> er;
        vector<int> ans;
        for(auto pi:aint[nod][tip])
        {
            if(viz[pi.second])
            {
                er.push_back(pi);
                continue;
            }
            if(pi.first>cmp) break;
            er.push_back(pi);
            ans.push_back(pi.second);
        }
        for(auto x:er)
        {
            aint[nod][tip].erase(x);
        }
        return ans;
    }
    int mid=(l+r)/2;
    if(dr<=mid) return query(2*nod,l,mid,st,dr,cmp,tip);
    else if(mid<st) return query(2*nod+1,mid+1,r,st,dr,cmp,tip);
    else
    {
        vector<int> vst=query(2*nod,l,mid,st,mid,cmp,tip);
        vector<int> vdr=query(2*nod+1,mid+1,r,mid+1,dr,cmp,tip);
        if(vst.size()>vdr.size())
        {
            for(int x:vdr) vst.push_back(x);
            return vst;
        }
        for(int x:vst) vdr.push_back(x);
        return vdr;
    }
}
signed main()
{
    int n,m;
    cin>>n>>m;
    priority_queue<pair<int,int>> pq;
    bool ok=1;
    for(int i=1;i<=m;i++)
    {
        cin>>trat[i].t>>trat[i].l>>trat[i].r>>trat[i].c;
        nrm[trat[i].t]=0;
        if(trat[i].t!=1) ok=0;
        if(trat[i].l==1)
        {
            pq.push({-trat[i].c,i});
            viz[i]=1;
        }
    }
    int cnt=1;
    for(auto [timp,v]:nrm)
    {
        nrm[timp]=cnt;
        cnt++;
    }
    cnt--;
    for(int i=1;i<=m;i++)
    {
        intime[nrm[trat[i].t]].push_back(i);
    }
    build(1,1,cnt);
    /*
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j==i) continue;
            if(trat[i].t<trat[j].t)
            {
                if(trat[i].r+trat[i].t>=trat[j].l+trat[j].t-1) g[i].push_back({j,trat[j].c});
            }
            else
            {
                 if(trat[i].r-trat[i].t>=trat[j].l-trat[j].t-1) g[i].push_back({j,trat[j].c});
            }
        }
    }*/
    while(!pq.empty())
    {
        auto [val,nod]=pq.top();
        pq.pop();
        if(trat[nod].r==n)
        {
            cout<<-val<<'\n';
            return 0;
        }
        vector<int> nxtnodes1;
        if(nrm[trat[nod].t]+1<=cnt) nxtnodes1=query(1,1,cnt,nrm[trat[nod].t]+1,cnt,trat[nod].r+trat[nod].t,1);
        vector<int> nxtnodes2=query(1,1,cnt,1,nrm[trat[nod].t],trat[nod].r-trat[nod].t,2);
        for(int u:nxtnodes1)
        {
            pq.push({val-trat[u].c,u});
            viz[u]=1;
        }
        for(int u:nxtnodes2)
        {
            pq.push({val-trat[u].c,u});
            viz[u]=1;
        }
    }
    cout<<-1<<'\n';
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61