Submission #21084

#	Time	Username	Problem	Language	Result	Execution time	Memory
21084		sbansalcs	Pinball (JOI14_pinball)	C++14	100 / 100	413 ms	45680 KiB

pinball

#include <iostream>
#include <vector>
#include <map>
#include <assert.h>
#include <algorithm>
using namespace std;
typedef long long ll;
#define mid (start+end)/2

const int M = 1e5+5;
const int N = M*3;
const ll inf=1e15;
ll dp[2][M];
int A[M][3];
int act[M*3];
ll D[M];
map<int,int> mp;
ll TREE[2][N*4];
void build(int idx, int start, int end) {
    TREE[0][idx]=TREE[1][idx]=inf;
    if(start!=end)  {
        build(idx*2, start, mid);
        build(idx*2+1, mid+1, end);
    }
}
void update(int g, int idx, int start, int end, int x, ll v)   {
    if(start==end)  {
        TREE[g][idx]=min(TREE[g][idx],v);
        return;
    }
    else if(x<=mid) update(g, idx*2, start, mid, x, v);
    else    update(g, idx*2+1, mid+1, end, x, v);
    TREE[g][idx]=min(TREE[g][idx*2],TREE[g][idx*2+1]);
}

ll query(int g, int idx, int start, int end , int a, int b) {
    if(start>=a && end<=b)  return TREE[g][idx];
    else if(start>b || end<a)   return inf;
    else    return min(query(g,idx*2,start,mid,a,b),query(g,idx*2+1,mid+1,end,a,b));
}



int main() {
    vector<pair<int, pair<int, int>>> vt;
    int m,n,x;scanf("%d %d",&m,&n);
    for (int i=1; i<=m; i++) {
        scanf("%d",&x);
        vt.push_back({x,{i,0}});
        scanf("%d",&x);
        vt.push_back({x,{i,1}});
        scanf("%d",&x);
        vt.push_back({x,{i,2}});
        scanf("%lld",D+i);
    }
    vt.push_back({1,{0,3}});
    vt.push_back({n,{0,3}});
    sort(vt.begin(),vt.end());
    int i=0,h,g=0;
    while (i<vt.size()) {
        h=vt[i].first;
        g++;
        act[g]=h;
        mp[h]=g;
        while (i<vt.size() && h==vt[i].first) {
            if(vt[i].second.second>=3)  {
                i++;    continue;
            }
            A[vt[i].second.first][vt[i].second.second]=g;
            i++;
        }
    }
    n=mp[n];
    build(1, 1, g);
    ll ans=inf;
    for (int i=1; i<=m; i++) {
        if(A[i][0]==1)  {
            dp[0][i]=D[i];
        }
        else    {
            dp[0][i]=D[i]+query(0,1,1,g,A[i][0],A[i][1]);
        }
        if(A[i][1]==n)  {
            dp[1][i]=D[i];
        }
        else    {
            dp[1][i]=D[i]+query(1,1,1,g,A[i][0],A[i][1]);
        }
        ans=min(ans,dp[1][i]+dp[0][i]-D[i]);
        update(0, 1, 1, g, A[i][2], dp[0][i]);
        update(1, 1, 1, g, A[i][2], dp[1][i]);
    }
    if(ans>=inf)    ans=-1;
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:60:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i<vt.size()) {
             ^
pinball.cpp:65:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i<vt.size() && h==vt[i].first) {
                 ^
pinball.cpp:46:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int m,n,x;scanf("%d %d",&m,&n);
                                   ^
pinball.cpp:48:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
pinball.cpp:50:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
pinball.cpp:52:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
pinball.cpp:54:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",D+i);
                          ^

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