Submission #423929

#	Time	Username	Problem	Language	Result	Execution time	Memory
423929		kai824	Treatment Project (JOI20_treatment)	C++17	0 / 100	629 ms	524292 KiB

treatment

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define int long long
typedef pair<int,int> pii;
#define mp make_pair
#define eb emplace_back

const int mxm=100005,inf=1e17;

pair<pii,pii> pts[mxm];int nex=0;
vector<pair<int,pii> >endds;

struct inn{
  int s,e,v=inf;
  inn *l,*r;
  inn(int ss,int ee){
    s=ss;e=ee;
    l=r=NULL;
  }
  int query(int p){
    if(p<=s)return v;
    int ans=inf;
    if(p<=(s+e)/2){
      if(l)ans=l->query(p);
    }
    if(r)ans=min(ans,r->query(p));
    return ans;
  }
  void update(int p,int nv){
    //cout<<"inn update "<<s<<' '<<e<<' '<<p<<'\n';
    v=min(v,nv);
    if(s==e){
      return;
    }
    if(p<=(s+e)/2){
      if(!l)l=new inn(s,(s+e)/2);
      l->update(p,nv);
    }else{
      if(!r)r=new inn((s+e)/2+1,e);
      r->update(p,nv);
    }
  }
};

struct node{
  int s,e;
  node *l,*r;
  inn *inne;
  node(int ss,int ee,int s2,int e2){//min queries...
    s=ss;e=ee;
    l=r=NULL;
    inne=new inn(s2,e2);
  }
  void update(int a,int b,int c){
    if(s==1 && e==2e9+2)b+=1e9+3;
    inne->update(b,c);
    if(s==e)return;

    if(a<=(s+e)/2){
      if(!l)l=new node(s,(s+e)/2,inne->s,inne->e);
      l->update(a,b,c);
    }else{
      if(!r)r=new node((s+e)/2+1,e,inne->s,inne->e);
      r->update(a,b,c);
    }
  }
  int query(int a,int b){
    if(s==1 && e==2e9+2)b+=1e9+3;
    if(a<=s){
      return inne->query(b);
    }
    int ans=inf;
    if(a<=(s+e)/2){if(l)ans=l->query(a,b);}
    if(r)ans=min(ans,r->query(a,b));
    return ans;
  }
} *root;

int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int n,m,ans=inf;
  cin>>n>>m;

  root=new node(0,2e9+2,1,2e9+3);

  for(int i=0;i<m;i++){
    int t,l,r,c;
    cin>>t>>l>>r>>c;r++;
    if(l==1){
      root->update(t+r,-t+r,c);//1 to 2e9, and -1e9 to 1e9
    }else if(r==n+1){
      endds.eb(c,mp(t+l,-t+l));
    }
    if(l==1 && r==n)ans=min(ans,c);
    if(l>1 && r<n)pts[nex++]=mp(mp(r,l),mp(t,c));
  }
  sort(pts,pts+nex);//increasing r...
  for(int i=0;i<nex;i++){
    //query upper-right corner:(t+l,-t+l)
    auto x=pts[i];
    int dist=root->query(x.s.f+x.f.s,-x.s.f+x.f.s);//query from bottom left
    root->update(x.s.f+x.f.f,-x.s.f+x.f.f,dist+x.s.s);//update on square top right corner...
  }
  for(auto x:endds){
    ans=min(ans,x.f+root->query(x.s.f,x.s.s) );
  }

  if(ans==inf)cout<<"-1\n";
  else cout<<ans<<'\n';
}

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