Submission #77746

#	Time	Username	Problem	Language	Result	Execution time	Memory
77746		nxteru	Pinball (JOI14_pinball)	C++14	0 / 100	16 ms	17144 KiB

pinball

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
ll n,m,k,x[100005],y[100005],z[100005],d[100005],seg[2][1<<20],ans=INF;
vector<ll>cm;
map<ll,ll>pr;
void ini(void){
    for(int i=0;i<1<<20;i++){
        seg[0][i]=INF;
        seg[1][i]=INF;
    }
}
void up(int s,int a,ll b){
    a+=(1<<19)-1;
    seg[s][a]=min(seg[s][a],b);
    while(a>0){
        a=(a-1)/2;
        seg[s][a]=min(seg[s][a*2+1],seg[s][a*2+2]);
    }
}
ll que(int s,int a,int b,int l,int r,int o){
    if(r<a||b<l)return INF;
    if(a<=l&&r<=b)return seg[s][o];
    return min(que(s,a,b,l,(l+r-1)/2,o*2+1),que(s,a,b,(l+r+1)/2,r,o*2+2));
}
int main(void){
    scanf("%lld%lld",&n,&m);
    cm.PB(1);
    cm.PB(m);
    for(int i=0;i<n;i++){
        scanf("%lld%lld%lld%lld",x+i,y+i,z+i,d+i);
        cm.PB(x[i]);
        cm.PB(y[i]);
        cm.PB(z[i]);
    }
    sort(cm.begin(),cm.end());
    cm.erase(unique(cm.begin(),cm.end()),cm.end());
    k=cm.size();
    for(int i=0;i<k;i++)pr[cm[i]]=i;
    for(int i=0;i<n;i++){
        x[i]=pr[x[i]];
        y[i]=pr[y[i]];
        z[i]=pr[z[i]];
    }
    m=pr[m];
    ini();
    up(0,0,0);
    up(1,m,0);
    for(int i=0;i<n;i++){
        ans=min(ans,que(0,x[i],y[i],0,(1<<19)-1,0)+que(1,x[i],y[i],0,(1<<19)-1,0)+d[i]);
        up(0,z[i],que(0,x[i],y[i],0,(1<<19)-1,0)+d[i]);
        up(1,z[i],que(1,x[i],y[i],0,(1<<19)-1,0)+d[i]);
    }
    printf("%lld\n",ans);
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~
pinball.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld%lld",x+i,y+i,z+i,d+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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