Submission #1079541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079541		isaachew	Treatment Project (JOI20_treatment)	C++17	0 / 100	654 ms	524288 KiB

treatment

#include <bits/stdc++.h>
/*
 A project at L and R are necessary
 Projects "chain"
 Turn the projects into a graph?
 
 35 points - Dijkstra from left project to right project
 */
struct project{
    long long l,r,t,c;
};

struct segtree{
    std::vector<std::vector<int>> value;
    std::vector<int> left,right;
    std::vector<int> isleaf;
    segtree(){
        value.push_back(std::vector<int>());
        isleaf.push_back(1);
        left.push_back(0);right.push_back(0);
    }
    void update(long long l,long long r,int v,long long nl=-2e9,long long nr=2e9,int ni=0){
        //std::cout<<"update "<<nl<<' '<<nr<<' '<<ni<<' '<<left[ni]<<' '<<right[ni]<<'\n';
        if(r<l)return;//??
        if(r<=nl||l>=nr)return;
        if(l<=nl&&r>=nr){
            value[ni].push_back(v);
            return;
        }
        long long nm=(nl+nr)/2;
        if(isleaf[ni]){
            left[ni]=value.size();
            value.push_back(std::vector<int>());
            isleaf.push_back(1);left.push_back(0);right.push_back(0);
            right[ni]=value.size();
            value.push_back(std::vector<int>());
            isleaf.push_back(1);left.push_back(0);right.push_back(0);
            isleaf[ni]=0;
        }
        update(l,r,v,nl,nm,left[ni]);
        update(l,r,v,nm,nr,right[ni]);
    }
    void query(long long pos,int from,bool neg,std::vector<int>& vec,long long nl=-2e9,long long nr=2e9,int ni=0){
        while(!value[ni].empty()&&(neg?value[ni].back()>from:value[ni].back()<from)){
            vec.push_back(value[ni].back());
            value[ni].pop_back();
        }
        if(!isleaf[ni]){
            long long nm=(nl+nr)/2;
            if(pos<nm){
                query(pos,from,neg,vec,nl,nm,left[ni]);
            }else{
                query(pos,from,neg,vec,nm,nr,right[ni]);
            }
        }
    }
};

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,m;
    std::cin>>n>>m;
    std::vector<project> projs;
    segtree pasts;//stores left - time
    segtree futures;//stores left - time
    for(int i=0;i<m;i++){
        int a,b,c,d;
        project pr;
        std::cin>>a>>b>>c>>d;
        pr.t=a;pr.l=b;pr.r=c;pr.c=d;
        projs.push_back(pr);
    }
    
    std::sort(projs.begin(),projs.end(),[&](project a,project b){return a.t<b.t;});
    for(int i=m;i--;){
        pasts.update(projs[i].l-projs[i].t-1,projs[i].r-projs[i].t+1,i);
    }
    for(int i=0;i<m;i++){
        futures.update(projs[i].l+projs[i].t-1,projs[i].r+projs[i].t+1,i);
    }
    std::vector<long long> dists(n,1e18);
    std::priority_queue<std::pair<long long,int>> dijkstra;
    for(int i=0;i<m;i++){
        if(projs[i].l==1){
            dijkstra.push({-projs[i].c,i});
        }
    }
    while(!dijkstra.empty()){
        std::pair<long long,int> cur=dijkstra.top();
        dijkstra.pop();
        if(dists[cur.second]<=-cur.first)continue;
        dists[cur.second]=-cur.first;
        int i=cur.second;
        std::vector<int> eds;
        pasts.query(projs[i].r-projs[i].t,i,0,eds);
        futures.query(projs[i].r+projs[i].t,i,1,eds);
        //std::cout<<"pasts\n";
        for(int i:eds){
            //std::cout<<i<<" from "<<cur.second<<'\n';
            dijkstra.push({cur.first-projs[i].c,i});
        }
        //std::cout<<"futures\n";
        
    }
    long long result=1e18;
    for(int i=0;i<m;i++){
        if(projs[i].r==n){
            //std::cout<<i<<'\n';
            result=std::min(result,dists[i]);
        }
    }
    std::cout<<(result==1e18?-1:result)<<'\n';
}

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