Submission #362265

#	Time	Username	Problem	Language	Result	Execution time	Memory
362265		denkendoemeer	Pinball (JOI14_pinball)	C++14	100 / 100	229 ms	23532 KiB

pinball

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int a[100005],b[100005],c[100005],d[100005],e[400005];
ll r1[1<<20],r2[1<<20];
void add(ll *a,int poz,ll val)
{
    poz+=1<<19;
    while(poz){
        a[poz]=min(a[poz],val);
        poz/=2;
    }
}
ll rem(ll *a,int poz,int poz2)
{
    ll ans=1e18;
    poz+=1<<19;
    poz2+=1<<19;
    while(poz<poz2){
        if (poz&1)
            ans=min(ans,a[poz++]);
        if (~poz2&1)
            ans=min(ans,a[poz2--]);
        poz=poz/2;
        poz2=poz2/2;
    }
    if (poz==poz2)
        ans=min(ans,a[poz]);
    return ans;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,m,i;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
    int u=0;
    e[u++]=1;
    e[u++]=m;
    for(i=0;i<n;i++){
        e[u++]=a[i];
        e[u++]=b[i];
        e[u++]=c[i];
    }
    sort(e,e+u);
    u=unique(e,e+u)-e;
    for(i=0;i<n;i++){
        a[i]=lower_bound(e,e+u,a[i])-e;
        b[i]=lower_bound(e,e+u,b[i])-e;
        c[i]=lower_bound(e,e+u,c[i])-e;
    }
    for(i=0;i<(1<<20);i++)
        r1[i]=r2[i]=1e18;
    add(r1,0,0);
    add(r2,u-1,0);
    ll ans=1e18;
    for(i=0;i<n;i++){
        ll aux1=rem(r1,a[i],b[i]),aux2=rem(r2,a[i],b[i]);
        add(r1,c[i],aux1+d[i]);
        add(r2,c[i],aux2+d[i]);
        ans=min(ans,aux1+aux2+d[i]);
    }
    if (ans==1e18)
        printf("-1\n");
    else
        printf("%lld\n",ans);
return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
pinball.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |         scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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