Submission #1079448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079448		isaachew	Treatment Project (JOI20_treatment)	C++17	0 / 100	614 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{
    long long nl,nr;
    segtree* left,*right;
    std::vector<int> value;
    bool isleaf;
    segtree(long long l,long long r,int v=-2){
        nl=l,nr=r;
        isleaf=1;
        left=right=NULL;
        if(v!=-2)value.push_back(v);
    }
    ~segtree(){
        if(!isleaf){
            delete left;
            delete right;
        }
    }
    void update(long long l,long long r,int v){
        //std::cout<<"update "<<nl<<' '<<nr<<'\n';
        if(l<=nl&&r>=nr){
            value.push_back(v);
            return;
        }
        if(r<=nl||l>=nr)return;
        long long nm=(nl+nr)/2;
        if(isleaf){
            left=new segtree(nl,nm,-2);
            right=new segtree(nm,nr,-2);
            isleaf=0;
        }
        left->update(l,r,v);
        right->update(l,r,v);
    }
    std::vector<int> query(long long pos,int from,bool neg){
        std::vector<int> cur;
        while(!value.empty()&&(neg?value.back()>from:value.back()<from)){
            cur.push_back(value.back());
            value.pop_back();
        }
        if(!isleaf){
            long long nm=(nl+nr)/2;
            if(pos<nm){
                for(int i:left->query(pos,from,neg)){
                    cur.push_back(i);
                }
            }else{
                for(int i:right->query(pos,from,neg)){
                    cur.push_back(i);
                }
            }
        }
        return cur;
    }
};

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(-2e9,2e9);//stores left - time
    segtree futures(-2e9,2e9);//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);
        std::vector<int> eds2=futures.query(projs[i].r+projs[i].t,i,1);
        //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";
        for(int i:eds2){
            //std::cout<<i<<" from "<<cur.second<<'\n';
            dijkstra.push({cur.first-projs[i].c,i});
        }
    }
    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