Submission #225782

#	Time	Username	Problem	Language	Result	Execution time	Memory
225782		MKopchev	Pinball (JOI14_pinball)	C++14	100 / 100	482 ms	72056 KiB

pinball

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

const int nmax=1e6+42;
const long long inf=1e18;

int n,m;

struct row
{
    int l,r,go,cost;
};

row inp[nmax];

long long tree[2][4*nmax];

void update(int which,int node,int l,int r,int pos,long long val)
{
    if(l==r)
    {
        tree[which][node]=min(tree[which][node],val);
        return;
    }

    int av=(l+r)/2;
    if(pos<=av)update(which,node*2,l,av,pos,val);
    else update(which,node*2+1,av+1,r,pos,val);

    tree[which][node]=min(tree[which][node],val);
}

long long query(int which,int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree[which][node];

    long long ret=inf;
    int av=(l+r)/2;

    if(lq<=av)ret=min(ret,query(which,node*2,l,av,lq,min(av,rq)));
    if(av<rq)ret=min(ret,query(which,node*2+1,av+1,r,max(av+1,lq),rq));
    return ret;
}
int help[nmax],pointer=0;

void add(int val)
{
    if(1>val||val>n)return;
    pointer++;
    help[pointer]=val;
}
void note(int val)
{
    add(val-1);
    add(val);
    add(val+1);
}

int where(int val)
{
    int pos=lower_bound(help+1,help+pointer+1,val)-help;
    return pos;
}
int main()
{
    scanf("%i%i",&m,&n);

    add(1);
    add(n);

    for(int i=1;i<=m;i++)
    {
        scanf("%i%i%i%i",&inp[i].l,&inp[i].r,&inp[i].go,&inp[i].cost);

        note(inp[i].l);
        note(inp[i].r);
        note(inp[i].go);
    }

    sort(help+1,help+pointer+1);

    //for(int i=1;i<=pointer;i++)cout<<help[i]<<" ";cout<<endl;

    for(int i=0;i<4*nmax;i++)
    {
        tree[0][i]=inf;
        tree[1][i]=inf;
    }

    update(0,1,1,pointer,where(1),0);

    update(1,1,1,pointer,where(n),0);

    long long output=inf;

    for(int i=1;i<=m;i++)
    {
        long long cost_0=query(0,1,1,pointer,where(inp[i].l),where(inp[i].r));
        long long cost_1=query(1,1,1,pointer,where(inp[i].l),where(inp[i].r));

        //use the current as a meeting point
        output=min(output,cost_0+cost_1+inp[i].cost);

        update(0,1,1,pointer,where(inp[i].go),cost_0+inp[i].cost);

        update(1,1,1,pointer,where(inp[i].go),cost_1+inp[i].cost);
    }

    if(output>=inf)printf("-1\n");
    else printf("%lld\n",output);
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&m,&n);
     ~~~~~^~~~~~~~~~~~~~
pinball.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i%i",&inp[i].l,&inp[i].r,&inp[i].go,&inp[i].cost);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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