oj.uz

Submission #21083

# Submission time Handle Problem Language Result Execution time Memory
21083 2017-04-04T12:58:25 Z sbansalcs Pinball (JOI14_pinball) C++14
100 / 100
 423 ms 45680 KB 
#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);
//        if(g==0 )           cout<<"HOLA UP: "<<start<<"  "<<x<<endl;

        
        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],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];
//    for (int i=1; i<=m; i++) {
//        cout<<i<<"  :  "<<A[i][0]<<"  "<<A[i][1]<<"  "<<A[i][2]<<endl;
//    }
    
    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]);
//            cout<<i<<"  :  "<<query(0,1,1,g,A[i][0],A[i][1])<<endl;
//            cout<<"queried :   "<<A[i][0]<<"  "<<A[i][1]<<"  -- "<<query(0,1,1,g,A[i][0],A[i][1])<<endl;
        }
        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]);
//            cout<<"queried: 1 :   "<<A[i][0]<<"  "<<A[i][1]<<"  -- "<<query(1,1,1,g,A[i][0],A[i][1])<<endl;

        }
        ans=min(ans,dp[1][i]+dp[0][i]-D[i]);
        update(0, 1, 1, g, A[i][2], dp[0][i]);
//        cout<<"UP :  "<<A[i][2]<<"  --  "<<dp[0][i]<<endl;
        update(1, 1, 1, g, A[i][2], dp[1][i]);
//        cout<<"UP : 1  "<<A[i][2]<<"  --  "<<dp[1][i]<<endl;

//        cout<<i<<"  "<<dp[0][i]<<"  "<<dp[1][i]<<endl;
    }
    if(ans>=inf)    ans=-1;
    cout<<ans<<endl;
    return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:70:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i<vt.size()) {
             ^
pinball.cpp:75:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i<vt.size() && h==vt[i].first) {
                 ^
pinball.cpp:56: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:58:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
pinball.cpp:60:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
pinball.cpp:62:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
pinball.cpp:64: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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 25464 KB Output is correct
2 Correct 0 ms 25464 KB Output is correct
3 Correct 0 ms 25464 KB Output is correct
4 Correct 0 ms 25464 KB Output is correct
5 Correct 0 ms 25464 KB Output is correct
6 Correct 0 ms 25464 KB Output is correct
7 Correct 0 ms 25464 KB Output is correct
8 Correct 0 ms 25464 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 25464 KB Output is correct
2 Correct 0 ms 25464 KB Output is correct
3 Correct 0 ms 25464 KB Output is correct
4 Correct 0 ms 25464 KB Output is correct
5 Correct 0 ms 25464 KB Output is correct
6 Correct 0 ms 25464 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 25464 KB Output is correct
2 Correct 0 ms 25464 KB Output is correct
3 Correct 0 ms 25636 KB Output is correct
4 Correct 0 ms 25636 KB Output is correct
5 Correct 0 ms 25636 KB Output is correct
6 Correct 3 ms 25636 KB Output is correct
7 Correct 0 ms 25596 KB Output is correct
8 Correct 0 ms 25636 KB Output is correct
9 Correct 0 ms 25636 KB Output is correct
10 Correct 0 ms 25636 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 26720 KB Output is correct
2 Correct 69 ms 29588 KB Output is correct
3 Correct 243 ms 33368 KB Output is correct
4 Correct 216 ms 34764 KB Output is correct
5 Correct 163 ms 32840 KB Output is correct
6 Correct 246 ms 34764 KB Output is correct
7 Correct 353 ms 39476 KB Output is correct
8 Correct 273 ms 37232 KB Output is correct
9 Correct 56 ms 28952 KB Output is correct
10 Correct 186 ms 35612 KB Output is correct
11 Correct 293 ms 45680 KB Output is correct
12 Correct 419 ms 45680 KB Output is correct
13 Correct 423 ms 45680 KB Output is correct
14 Correct 356 ms 45680 KB Output is correct