Submission #1083180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083180		isaachew	Treatment Project (JOI20_treatment)	C++17	100 / 100	1746 ms	175984 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{
	int size;
    std::vector<std::vector<int>> value;
    std::vector<int> left,right;
    std::vector<int> isleaf;
	segtree(){}
    void init(int n){
		size=n;
        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,long long nr,int ni){
        //std::cout<<"update "<<nl<<' '<<nr<<' '<<ni<<' '<<left[ni]<<' '<<right[ni]<<'\n';
        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 update(long long l,long long r,int v){update(l,r,v,0,size,0);}
    void query(long long pos,int from,bool neg,std::vector<int>& vec,long long nl,long long nr,int ni){
        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]);
            }
        }
    }
	void query(long long pos,int from,bool neg,std::vector<int>& vec){query(pos,from,neg,vec,0,size,0);}
};

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;});
    std::set<int> plist;
    std::map<int,int> places;
    for(int i=m;i--;){
        plist.insert(projs[i].l-projs[i].t-1);
		plist.insert(projs[i].r-projs[i].t+1);
    }
    for(int i=0;i<m;i++){
        plist.insert(projs[i].l+projs[i].t-1);
        plist.insert(projs[i].r+projs[i].t+1);
    }
	int j=0;
    for(int i:plist){
		places[i]=j++;
		
    }
	pasts.init(plist.size());
	futures.init(plist.size());
	for(int i=m;i--;){
		pasts.update(places[projs[i].l-projs[i].t-1],places[projs[i].r-projs[i].t+1],i);
	}
	for(int i=0;i<m;i++){
		futures.update(places[projs[i].l+projs[i].t-1],places[projs[i].r+projs[i].t+1],i);
	}
    std::vector<long long> dists(m,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(places[(projs[i].r-projs[i].t)+1]-1,i,0,eds);
        futures.query(places[(projs[i].r+projs[i].t)+1]-1,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: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61