Submission #152597

#	Time	Username	Problem	Language	Result	Execution time	Memory
152597		karma	Pinball (JOI14_pinball)	C++14	100 / 100	442 ms	32620 KiB

pinball

#include<bits/stdc++.h>
#define pb      emplace_back
#define mp      make_pair
#define fi      first
#define se      second
#define ll      long long

using namespace std;

const int N = int(3e5) + 7;
const ll inf = (ll)1e18;

struct TDevice {
    int l, r, pos;
    ll cost;
} d[N];
ll st[N << 2][2], res, f[2];
int n, m, l[N << 2], h[N << 2];
vector<int> v;

void Build(int x, int low, int high) {
    l[x] = low, h[x] = high;
    st[x][0] = st[x][1] = inf;
    if(l[x] == h[x]) return;
    int mid = (low + high) >> 1;
    Build(x << 1, low, mid);
    Build(x << 1 | 1, mid + 1, high);
}

void Update(int x, int pos, ll cost, bool type) {
    if(l[x] > pos || h[x] < pos) return;
    if(l[x] == h[x]) {
       st[x][type] = min(st[x][type], cost);
       return;
    }
    Update(x << 1, pos, cost, type);
    Update(x << 1 | 1, pos, cost, type);
    st[x][type] = min(st[x << 1][type], st[x << 1 | 1][type]);
}

ll Query(int x, int low, int high, bool type) {
    if(l[x] > high || h[x] < low) return inf;
    if(l[x] >= low && h[x] <= high) return st[x][type];
    return min(Query(x << 1, low, high, type), Query(x << 1 | 1, low, high, type));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> m >> n;
    for(int i = 0; i < m; ++i) {
        cin >> d[i].l >> d[i].r >> d[i].pos >> d[i].cost;
        v.pb(d[i].l), v.pb(d[i].r), v.pb(d[i].pos);
    }
    v.pb(1), v.pb(n); res = inf;
    sort(v.begin(), v.end());
    Build(1, 1, int(v.size()));
    for(int i = 0; i < m; ++i) {
        d[i].l = lower_bound(v.begin(), v.end(), d[i].l) - v.begin() + 1;
        d[i].r = lower_bound(v.begin(), v.end(), d[i].r) - v.begin() + 1;
        d[i].pos = lower_bound(v.begin(), v.end(), d[i].pos) - v.begin() + 1;
        if(v[d[i].r - 1] == n) f[1] = 0;
        else f[1] = Query(1, d[i].l, d[i].r, 1);
        if(v[d[i].l - 1] == 1) f[0] = 0;
        else f[0] = Query(1, d[i].l, d[i].r, 0);
        //cout << f[1] << ' ' << f[0] << '\n';
        res = min(res, f[0] + f[1] + d[i].cost);
        Update(1, d[i].pos, f[0] + d[i].cost, 0);
        Update(1, d[i].pos, f[1] + d[i].cost, 1);
    }
    if(res == inf) res = -1;
    cout << res;
}

Compilation message (stderr)

pinball.cpp: In function 'int main()':
pinball.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pinball.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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