Submission #216318

#	Time	Username	Problem	Language	Result	Execution time	Memory
216318		model_code	Treatment Project (JOI20_treatment)	C++17	100 / 100	241 ms	34136 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SIZE 1024*128
#define INF 1000000001
#define INFL 1000000000000000LL
struct T{
    int x,y,i;
    bool operator<(const T&q)const{
        if(x!=q.x)return x<q.x;
        if(y!=q.y)return y<q.y;
        return i<q.i;        
    }
};
struct segtree{
    vector<pair<int,int>>seg[SIZE*2];
    int sz,cx[SIZE],pt[SIZE*2];
    void init(int n){
        sz=1;
        while(sz<n)sz*=2;
        for(int i=0;i<sz*2;i++)seg[i].clear();
        for(int i=0;i<sz;i++)cx[i]=INF;
        for(int i=0;i<sz*2;i++)pt[i]=0;
    }
    void put(vector<T>q){
        for(int i=0;i<q.size();i++){
            cx[i]=q[i].x;
            seg[i+sz-1].push_back(pair<int,int>(q[i].y,q[i].i));
        }       
    }
    void build(int l,int r,int k){
        if(l==r)return;
        build(l,(l+r-1)/2,k*2+1);
        build((l+r+1)/2,r,k*2+2);
        seg[k].resize(seg[k*2+1].size()+seg[k*2+2].size());
        merge(seg[k*2+1].begin(),seg[k*2+1].end(),seg[k*2+2].begin(),seg[k*2+2].end(),seg[k].begin());
    }
    void query(int x,int y,int l,int r,int k,vector<int>&res){
        if(cx[r]<=x){
            while(pt[k]<seg[k].size()&&seg[k][pt[k]].first<=y){
                res.push_back(seg[k][pt[k]].second);
                pt[k]++;
            }
            return;
        }
        if(x<cx[l])return;
        query(x,y,l,(l+r-1)/2,k*2+1,res);
        query(x,y,(l+r+1)/2,r,k*2+2,res);
    }
};
int main(void){
    int n,m;
    ll ans=INFL;
    scanf("%d%d",&n,&m);
    vector<int>t(m),l(m),r(m);
    vector<ll>c(m),d(m);
    vector<T>p(m);
    vector<bool>pushed(m);
    static segtree seg;
    seg.init(m);
    for(int i=0;i<m;i++){
        scanf("%d%d%d%lld",&t[i],&l[i],&r[i],&c[i]);
        p[i]=(T{l[i]-t[i],l[i]+t[i],i});
    }
    sort(p.begin(),p.end());
    seg.put(p);
    seg.build(0,seg.sz-1,0);
    priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >dik;
    for(int i=0;i<m;i++){
        pushed[i]=false;
        d[i]=INFL;
        if(l[i]==1){
            d[i]=c[i];
            dik.push(pair<ll,int>(c[i],i));
            pushed[i]=true;
        }
    }
    while(!dik.empty()){
        int v=dik.top().second;
        ll dis=dik.top().first;
        dik.pop();
        vector<int>lis;
        lis.clear();
        seg.query(r[v]+1-t[v],r[v]+1+t[v],0,seg.sz-1,0,lis);
        for(int i=0;i<lis.size();i++){
            int u=lis[i];
            if(!pushed[u]){
                d[u]=dis+c[u];
                dik.push(pair<ll,int>(d[u],u));
                pushed[u]=true;
            }
        }
    }
    for(int i=0;i<m;i++){
        if(r[i]==n)ans=min(ans,d[i]);
    }
    if(ans==INFL)printf("-1\n");
    else printf("%lld\n",ans);
}

Compilation message (stderr)

treatment.cpp: In member function 'void segtree::put(std::vector<T>)':
treatment.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<q.size();i++){
                     ~^~~~~~~~~
treatment.cpp: In member function 'void segtree::query(int, int, int, int, int, std::vector<int>&)':
treatment.cpp:40:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(pt[k]<seg[k].size()&&seg[k][pt[k]].first<=y){
                   ~~~~~^~~~~~~~~~~~~~
treatment.cpp: In function 'int main()':
treatment.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<lis.size();i++){
                     ~^~~~~~~~~~~
treatment.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
treatment.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%lld",&t[i],&l[i],&r[i],&c[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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