Submission #876417

#	Time	Username	Problem	Language	Result	Execution time	Memory
876417		winter0101	Treatment Project (JOI20_treatment)	C++14	100 / 100	440 ms	56932 KiB

treatment

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=1e5+9;
struct edg{
int time;
int l,r;
long long c;
bool operator < (const edg &p)const {
return time<p.time;
}
}a[maxn];
vector<int>g[maxn];
/*bool check(int i, int j) {
    if (a[i].r == n)return 0;
    if (a[i].time <= a[j].time) {
        if (a[i].r+1+a[i].time>=a[j].l+a[j].time)return 1;
        return 0;
    } else {
        //will infected from a[j].l-1
        if (a[i].r+1-a[i].time>=a[j].l-a[j].time)return 1;
        return 0;
    }
}*/
int n,m;
long long d[maxn];
bool vis[maxn];
const long long inf=1e18;
struct line{
int u;
long long val;
bool operator < (const line &p)const {
return val>p.val;
}
};
vector<int>stx[maxn*4],sty[maxn*4];//x for case 1 y for case 2
void build(int id,int l,int r){
for1(i,l,r)stx[id].pb(i);
for1(i,l,r)sty[id].pb(i);
sort(all(stx[id]),[](int i,int j){
return a[i].l+a[i].time>a[j].l+a[j].time;
});
sort(all(sty[id]),[](int i,int j){
return a[i].l-a[i].time>a[j].l-a[j].time;
});
if (l==r)return;
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
priority_queue<line>t;
void get(int id,int l,int r,int u,int v,int root,bool fl){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
while (!stx[id].empty()){
if (fl)break;
int tmp=stx[id].back();
if (vis[tmp]){
    stx[id].pop_back();
    continue;
}
if (a[tmp].l+a[tmp].time<=a[root].r+1+a[root].time){
vis[tmp]=1;
d[tmp]=d[root]+a[tmp].c;
t.push({tmp,d[tmp]});
stx[id].pop_back();
}
else break;
}
while (!sty[id].empty()){
if (!fl)break;
int tmp=sty[id].back();
if (vis[tmp]){
    sty[id].pop_back();
    continue;
}
if (a[tmp].l-a[tmp].time<=a[root].r+1-a[root].time){
vis[tmp]=1;
d[tmp]=d[root]+a[tmp].c;
t.push({tmp,d[tmp]});
sty[id].pop_back();
}
else break;
}
return;
}
int mid=(l+r)/2;
get(id*2,l,mid,u,v,root,fl);
get(id*2+1,mid+1,r,u,v,root,fl);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>m;
    for1(i,1,m)cin>>a[i].time>>a[i].l>>a[i].r>>a[i].c;
    sort(a+1,a+1+m);
    build(1,1,m);
    for1(i,1,m)d[i]=inf;
    for1(i,1,m){
    if (a[i].l==1){
    t.push({i,a[i].c});
    d[i]=a[i].c;
    vis[i]=1;
    }
    }
    while (!t.empty()){
    auto u=t.top();
    t.pop();
    get(1,1,m,1,u.u-1,u.u,1);
    get(1,1,m,u.u+1,m,u.u,0);
    }
    long long ans=inf;
    for1(i,1,m)if (a[i].r==n)ans=min(ans,d[i]);
    if (ans>=inf)ans=-1;
    cout<<ans;
}

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