Submission #314361

#	Time	Username	Problem	Language	Result	Execution time	Memory
314361		ivan_tudor	Pinball (JOI14_pinball)	C++14	100 / 100	629 ms	95736 KiB

pinball

#include<bits/stdc++.h>
using namespace std;
const long long INF = LLONG_MAX;
struct AINT_node{
  int l,r;
  long long val;
  AINT_node *ls,*rs;
  AINT_node(int _l,int _r){
    l = _l;
    r= _r;
    val = INF;
    ls = rs = NULL;
  }
  void merg(){
    val = INF;
    if(rs!=NULL){
      val = min(val, rs->val);
    }
    if(ls!=NULL){
      val = min(val, ls->val);
    }
  }
};

void add(AINT_node *nod, int poz, long long val){
  if(nod->l == nod->r){
    nod->val =min(nod->val,val);
    return;
  }
  int mid = (nod->l + nod->r) / 2;
  if(poz <= mid){
    if(nod->ls == NULL){
      nod->ls = new AINT_node(nod->l,mid);
    }
    add(nod->ls,poz,val);
  }
  else{
    if(nod->rs == NULL){
      nod->rs = new AINT_node(mid+1, nod->r);
    }
    add(nod->rs,poz,val);
  }
  (*nod).merg();
}
long long query(AINT_node *nod,int ql,int qr){
  if(nod->r < ql || nod->l > qr){
    return INF;
  }
  if(ql <= nod->l && nod->r <=qr)
    return nod->val;
  long long lrsp, rrsp;
  if(nod->ls != NULL)
    lrsp = query(nod->ls, ql, qr);
  else
    lrsp = INF;
  if(nod -> rs !=NULL)
    rrsp = query(nod->rs , ql, qr);
  else
    rrsp = INF;
  return min(lrsp,rrsp);
}
const int M_MAX = 100005;
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int m,n;
  cin>>m>>n;
  AINT_node *st = new AINT_node(1,n);
  AINT_node *dr = new AINT_node(1,n);
  long long ans = INF;
  for(int i=1;i<=m;i++){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    long long dpst,dpdr;
    if(a == 1)
      dpst = 0;
    else
      dpst = query(st, a, b);
    if(b == n)
      dpdr = 0;
    else
      dpdr = query(dr, a, b);
    if(dpst != INF)
      dpst +=  d;
    if(dpdr != INF)
      dpdr += d;
    if(dpst != INF && dpdr != INF)
      ans = min(ans, dpst + dpdr - d);
    if(dpst != INF)
      add(st, c, dpst);
    if(dpdr != INF)
      add(dr, c, dpdr);
  }
  if(ans == INF){
    cout<<-1;
    return 0;
  }
  cout<<ans;
  return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49