Submission #54684

#	Time	Username	Problem	Language	Result	Execution time	Memory
54684		gs18081	Pinball (JOI14_pinball)	C++11	100 / 100	389 ms	61936 KiB

pinball

#include <bits/stdc++.h>
#define MAX 9999999999999999LL

using namespace std;

typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
struct thing{
    int A,B,C,D;
};
ll ans=MAX;
int N,M;
/*
set<pl> lmap;
set<pl> rmap;
*/
ll ltree[1200000];
ll rtree[1200000];
 vector<pair<int,pi> > vect;
thing things[110000];
void init(ll *tree,int l,int r,int idx){
    tree[idx]=MAX;
    if(l==r) return ;
    int m=(l+r)>>1;
    init(tree,l,m,idx*2);
    init(tree,m+1,r,idx*2+1);
}
ll range(ll *tree,int l,int r,int idx,int s,int e){
    if(r<s||e<l) return MAX;
    if(s<=l&&r<=e) return tree[idx];
    int m=(l+r)>>1;
    return min(range(tree,l,m,idx*2,s,e),range(tree,m+1,r,idx*2+1,s,e));
}
ll update(ll *tree,int l,int r,int idx,int pos,ll val){
    if(r<pos||pos<l) return tree[idx];
    if(l==r){
        return tree[idx]=min(tree[idx],val);
    }
    int m=(l+r)>>1;
    return tree[idx]=min(update(tree,l,m,idx*2,pos,val),update(tree,m+1,r,idx*2+1,pos,val));
}
int main(){
    scanf("%d %d",&M,&N);
    for(int i=0;i<M;i++){
        scanf("%d %d %d %d",&things[i].A,&things[i].C,&things[i].B,&things[i].D);
        vect.push_back(make_pair(things[i].A,pi(i,1)));
        vect.push_back(make_pair(things[i].B,pi(i,2)));
        vect.push_back(make_pair(things[i].C,pi(i,3)));
    }
    vect.push_back(make_pair(N,pi(0,0)));
    vect.push_back(make_pair(1,pi(0,0)));
    int x=1;
    sort(vect.begin(),vect.end());
    for(int i=0;i<vect.size();){
        int j;
        for(j=i;j<vect.size()&&vect[i].first==vect[j].first;j++){
            if(vect[j].second.second==0){
                
            }
            else if(vect[j].second.second==1){
                things[vect[j].second.first].A=x;
            }
            else if(vect[j].second.second==2){
                things[vect[j].second.first].B=x;
            }
            else{
                things[vect[j].second.first].C=x;
            }
        }
        x++;
        i=j;
    }
    x--;
    init(ltree,1,x,1);
    init(rtree,1,x,1);
    update(ltree,1,x,1,1,0);
    update(rtree,1,x,1,x,0);
    for(int i=0;i<M;i++){
        ans=min(ans,range(ltree,1,x,1,things[i].A,x)+range(rtree,1,x,1,1,things[i].C)+things[i].D);
        ll val;
        val=range(ltree,1,x,1,things[i].A,x)+things[i].D;
        update(ltree,1,x,1,things[i].B,val);
        val=range(rtree,1,x,1,1,things[i].C)+things[i].D;
        update(rtree,1,x,1,things[i].B,val);
        //printf("%d %d %d %d %d\n",things[i].A,things[i].B,things[i].C,things[i].D,x);
    }
    /*
    rmap.insert(pl(x-1,0));
    lmap.insert(pl(1,0));
    set<pl>::iterator lit;
    set<pl>::iterator rit;
    set<pl>::iterator temp;
    set<pl>::iterator ttemp;
    for(int i=0;i<M;i++){
        int l=things[i].A;
        int r=things[i].C;
        int m=things[i].B;
        lit=lmap.lower_bound(pl(l,-1));
        rit=rmap.upper_bound(pl(r,-1));
        if(lit!=lmap.end()&&rit!=rmap.begin()){
            --rit;
            ans=min((*lit).second+(*rit).second+things[i].D,ans);
            rit++;
        }
        if(lit!=lmap.end()){
            ll tval=(*lit).second+things[i].D;
            temp=lmap.lower_bound(pl(m,0));
            if(temp==lmap.end()||(*temp).second>tval){
                lmap.insert(pl(m,tval));
                temp=lmap.lower_bound(pl(m,0));
                temp--;
                while(temp!=lmap.begin()&&temp->second>=tval){
                    ttemp=temp--;
                    temp++;
                    lmap.erase(temp);
                    temp=ttemp;
                }
            }
            
        }
        if(rit!=rmap.begin()){
            --rit;
            ll tval=(*rit).second+things[i].D;
            temp=rmap.upper_bound(pl(m,0));
            if(temp==rmap.begin()){
                
            }
        }
    }
     */
    if(ans==MAX) printf("-1\n");
    else printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<vect.size();){
                 ~^~~~~~~~~~~~
pinball.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=i;j<vect.size()&&vect[i].first==vect[j].first;j++){
                 ~^~~~~~~~~~~~
pinball.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&M,&N);
     ~~~~~^~~~~~~~~~~~~~~
pinball.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d",&things[i].A,&things[i].C,&things[i].B,&things[i].D);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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