oj.uz

Submission #21084

# Submission time Handle Problem Language Result Execution time Memory
21084 2017-04-04T12:59:55 Z sbansalcs Pinball (JOI14_pinball) C++14
100 / 100
 413 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);
        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

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.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 0 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 3 ms 25636 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 26720 KB Output is correct
2 Correct 69 ms 29588 KB Output is correct
3 Correct 219 ms 33368 KB Output is correct
4 Correct 196 ms 34764 KB Output is correct
5 Correct 146 ms 32840 KB Output is correct
6 Correct 206 ms 34764 KB Output is correct
7 Correct 353 ms 39476 KB Output is correct
8 Correct 316 ms 37232 KB Output is correct
9 Correct 49 ms 28952 KB Output is correct
10 Correct 189 ms 35612 KB Output is correct
11 Correct 323 ms 45680 KB Output is correct
12 Correct 413 ms 45680 KB Output is correct
13 Correct 379 ms 45680 KB Output is correct
14 Correct 389 ms 45680 KB Output is correct