Submission #114952

#	Time	Username	Problem	Language	Result	Execution time	Memory
114952		Mercenary	Pinball (JOI14_pinball)	C++14	51 / 100	180 ms	22632 KiB

pinball

#include<bits/stdc++.h>

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
const int maxn = 1e5 + 5;

struct IT{
    ll s[maxn * 4];
    IT(){fill_n(s,maxn*4,(ll)1e18);};
    void update(int x , int l , int r , int id , ll val){
        if(l == r){
            s[x] = min(s[x] , val);
        }else{
            int mid = l + r >> 1;
            if(id <= mid)update(x * 2 , l , mid , id , val);
            else update(x * 2 + 1 , mid + 1 , r , id , val);
            s[x] = min(s[x * 2] , s[x * 2 + 1]);
        }
    }
    ll query(int x , int l , int r , int L , int R){
        if(L > r || l > R)return (ll)1e18;
        if(L <= l && r <= R){
            return s[x];
        }
        int mid = l + r >> 1;
        return min(query(x * 2 , l , mid , L , R) , query(x * 2 + 1 , mid + 1 , r , L , R));
    }
}s[2];

int m , n , a[maxn] , b[maxn] , c[maxn] , d[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> m >> n;
    vector<int> v;
    for(int i = 1 ; i <= m ; ++i){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        v.pb(a[i]);v.pb(b[i]);v.pb(c[i]);
    }
    v.pb(1);
    v.pb(n);
    sort(v.begin(),v.end());
    v.erase((unique(v.begin(),v.end())),v.end());
    n = v.size();
    s[0].update(1 , 1 , n , 1 , 0);
    s[1].update(1 , 1 , n , n , 0);
    ll res = (ll)1e18;
    for(int i = 1 ; i <= m ; ++i){
        int a = lower_bound(v.begin(),v.end(),::a[i]) - v.begin() + 1;
        int b = lower_bound(v.begin(),v.end(),::b[i]) - v.begin() + 1;
        int c = lower_bound(v.begin(),v.end(),::c[i]) - v.begin() + 1;
        ll lef = s[0].query(1 , 1 , n , a , b);
        ll rig = s[1].query(1 , 1 , n , a , b);
        cerr << lef + rig + d[i] << endl;
//        cerr << res << endl;
        res = min(res , lef + rig + d[i]);
        s[0].update(1 , 1 , n , c , lef + d[i]);
        s[1].update(1 , 1 , n , c , rig + d[i]);
    }
    cout << ((res == (ll)1e18) ? -1ll : res);
}

Compilation message (stderr)

pinball.cpp: In member function 'void IT::update(int, int, int, int, ll)':
pinball.cpp:23:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid = l + r >> 1;
                       ~~^~~
pinball.cpp: In member function 'll IT::query(int, int, int, int, int)':
pinball.cpp:34:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
pinball.cpp: In function 'int main()':
pinball.cpp:46:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pinball.cpp:47:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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