Submission #313523

#	Time	Username	Problem	Language	Result	Execution time	Memory
313523		alextodoran	Pinball (JOI14_pinball)	C++17	100 / 100	114 ms	16476 KiB

pinball

#include <bits/stdc++.h>
 
#define M_MAX 100002
#define N_MAX 300002
#define ll long long
 
using namespace std;
 
const ll INF = 100000000000000001;
 
struct Device
{
    int l, r;
    int hole;
    ll cost;
};
 
int n, m;
 
Device devices[M_MAX];
 
struct Object
{
    int pos;
    char type;
    int index;
};
bool operator < (const Object &a, const Object &b)
{
    return a.pos < b.pos;
}
 
vector <Object> objects;
 
ll dpL[M_MAX], dpR[M_MAX];
 
ll aibL[N_MAX], aibR[N_MAX];
 
void updateL (int pos, ll val)
{
    for(int i = pos; i >= 1; i -= i&(-i))
        aibL[i] = min(aibL[i], val);
}
 
void updateR (int pos, ll val)
{
    for(int i = pos; i <= n; i += i&(-i))
        aibR[i] = min(aibR[i], val);
}
 
ll queryL (int pos)
{
    ll ans = INF;
    for(int i = pos; i <= n; i += i&(-i))
        ans = min(ans, aibL[i]);
    return ans;
}
 
ll queryR (int pos)
{
    ll ans = INF;
    for(int i = pos; i >= 1; i -= i&(-i))
        ans = min(ans, aibR[i]);
    return ans;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> n;
    bool okL = false, okR = false;
    for(int i = 1; i <= m; i++)
    {
        cin >> devices[i].l >> devices[i].r >> devices[i].hole >> devices[i].cost;
        if(devices[i].l == 1)
            okL = true;
        if(devices[i].r == n)
            okR = true;
        objects.push_back(Object{devices[i].l, 'L', i});
        objects.push_back(Object{devices[i].r, 'R', i});
        objects.push_back(Object{devices[i].hole, 'H', i});
    }
    if(okL == false || okR == false)
    {
        cout << "-1\n";
        return 0;
    }
    sort(objects.begin(), objects.end());
    int pos = 1;
    for(int i = 0; i < objects.size(); i++)
    {
        if(i > 0 && objects[i].pos > objects[i - 1].pos)
            pos++;
        if(objects[i].type == 'L')
            devices[objects[i].index].l = pos;
        if(objects[i].type == 'R')
            devices[objects[i].index].r = pos;
        if(objects[i].type == 'H')
            devices[objects[i].index].hole = pos;
    }
    n = pos;
    for(int i = 0; i <= m; i++)
        dpL[i] = dpR[i] = INF;
    for(int i = 1; i <= m; i++)
    {
        if(devices[i].l == 1)
            dpL[i] = devices[i].cost;
        if(devices[i].r == n)
            dpR[i] = devices[i].cost;
    }
    for(int i = 1; i <= n; i++)
        aibL[i] = aibR[i] = INF;
    ll ans = INF;
    for(int i = 1; i <= m; i++)
    {
        if(dpL[i] == INF)
            dpL[i] = min(INF, queryL(devices[i].l) + devices[i].cost);
        if(dpR[i] == INF)
            dpR[i] = min(INF, queryR(devices[i].r) + devices[i].cost);
        updateL(devices[i].hole, dpL[i]);
        updateR(devices[i].hole, dpR[i]);
        ans = min(ans, dpL[i] + dpR[i] - devices[i].cost);
    }
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Object>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i = 0; i < objects.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~

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